CC

题目链接:点这里

题目

    在N*N的方格棋盘放置了N个皇后，使得它们不相互攻击（即任意2个皇后不允许处在同一排，同一列，也不允许处在与棋盘边框成45角的斜线上。 
你的任务是，对于给定的N，求出有多少种合法的放置方法。 

c++没有高精度类,很气,于是弄了一个高精度模板

Max Sum

Given a sequence a11,a22,a33......ann, your job is to calculate the max sum of a sub-sequence. For example, given (6,-1,5,4,-7), the max sum in this sequence is 6 + (-1) + 5 + 4 = 14. 

** 免费馅饼 **

都说天上不会掉馅饼，但有一天gameboy正走在回家的小径上，忽然天上掉下大把大把的馅饼。说来gameboy的人品实在是太好了，这馅饼别处都不掉，就掉落在他身旁的10米范围内。馅饼如果掉在了地上当然就不能吃了，所以gameboy马上卸下身上的背包去接。但由于小径两侧都不能站人，所以他只能在小径上接。由于gameboy平时老呆在房间里玩游戏，虽然在游戏中是个身手敏捷的高手，但在现实中运动神经特别迟钝，每秒种只有在移动不超过一米的范围内接住坠落的馅饼。现在给这条小径如图标上坐标： 

Brackets

We give the following inductive definition of a “regular brackets” sequence:

the empty sequence is a regular brackets sequence,
if s is a regular brackets sequence, then (s) and [s] are regular brackets sequences, and
if a and b are regular brackets sequences, then ab is a regular brackets sequence.

<!--more-->

no other sequence is a regular brackets sequence
For instance, all of the following character sequences are regular brackets sequences:

(), [], (()), ()[], ()[()]

while the following character sequences are not:

(, ], )(, ([)], ([(]

Given a brackets sequence of characters a1a2 … an, your goal is to find the length of the longest regular brackets sequence that is a subsequence of s. That is, you wish to find the largest m such that for indices i1, i2, …, im where 1 ≤ i1 < i2 < … < im ≤ n, ai1ai2 … aim is a regular brackets sequence.

Given the initial sequence ([([]])], the longest regular brackets subsequence is [([])].

Input

The input test file will contain multiple test cases. Each input test case consists of a single line containing only the characters (, ), [, and ]; each input test will have length between 1 and 100, inclusive. The end-of-file is marked by a line containing the word “end” and should not be processed.

Output

For each input case, the program should print the length of the longest possible regular brackets subsequence on a single line.

Sample Input

((()))
()()()
([]])
)[)(
([][][)
end

Sample Output

6
6
4
0
6

题意

给你一串字符串,判断有多少个括号配对

思路

1 类似POJ 1141 的那道括号匹配问题,这里我们只需要转换一下,求最少加上多少个括号就能使所有的括号匹配,然后用总长度减去需要加上的括号,极为匹配的括号,
dp[i][j]表示i道j最少需要加上多少个括号,

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

int const INF=0x3fffffff;
char s[205];
int dp[205][205];

int main(){
    while(scanf("%s",s)!=EOF&&strcmp(s,"end")!=0){
        memset(dp,0,sizeof(dp));
        int len=strlen(s);
        for(int i=0;i<len;++i)
            dp[i][i]=1;
        for(int k=1;k<len;++k)
        for(int i=0;i<len-1;++i){
            dp[i][i+k]=INF;
            if((s[i]=='('&&s[i+k]==')')||(s[i]=='['&&s[i+k]==']'))
                dp[i][i+k]=dp[i+1][i+k-1];
            for(int j=i;j<i+k;++j)
                dp[i][i+k]=min(dp[i][i+k],dp[i][j]+dp[j+1][i+k]);
        }
        printf("%d\n",len-dp[0][len-1]);
    }
    return 0;
}

Longest Ordered Subsequence

A numeric sequence of ai is ordered if a1 < a2 < ... < aN. Let the subsequence of the given numeric sequence ( a1, a2, ..., aN) be any sequence ( ai1, ai2, ..., aiK), where 1 <= i1 < i2 < ... < iK <= N. For example, sequence (1, 7, 3, 5, 9, 4, 8) has ordered subsequences, e. g., (1, 7), (3, 4, 8) and many others. All longest ordered subsequences are of length 4, e. g., (1, 3, 5, 8). 

Your program, when given the numeric sequence, must find the length of its longest ordered subsequence.

悼念512汶川大地震遇难同胞――珍惜现在，感恩生活

急！灾区的食物依然短缺！ 
为了挽救灾区同胞的生命，心系灾区同胞的你准备自己采购一些粮食支援灾区，现在假设你一共有资金n元，而市场有m种大米，每种大米都是袋装产品，其价格不等，并且只能整袋购买。 
请问：你用有限的资金最多能采购多少公斤粮食呢？ 

滑雪

Michael喜欢滑雪百这并不奇怪， 因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。Michael想知道载一个区域中最长底滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子


<!--more-->


 1  2  3  4 5

16 17 18 19 6

15 24 25 20 7

14 23 22 21 8

13 12 11 10 9

一个人可以从某个点滑向上下左右相邻四个点之一，当且仅当高度减小。在上面的例子中，一条可滑行的滑坡为24-17-16-1。当然25-24-23-...-3-2-1更长。事实上，这是最长的一条。

Input

输入的第一行表示区域的行数R和列数C(1 <= R,C <= 100)。下面是R行，每行有C个整数，代表高度h，0<=h<=10000。

Output

输出最长区域的长度。

Sample Input

5 5
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
1    4 23 22 21 8
13 12 11 10 9

Sample Output

25

思路

类似于记忆化搜索,dp[i][j]表示从(i,j)开始的所能走到的最大高度,最后遍历dp的所有值,找出最大的值.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>

using namespace std;
int w[110][110],dp[110][110];
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
int r,c;

int ff(int x,int y){
    if(dp[x][y])
        return dp[x][y];
    int t=1;//存储当前位置开始走所能走到的最大高度
    for(int i=0;i<4;++i){
        int sx=x+dx[i];
        int sy=y+dy[i];
        if(sx>0&&sy>0&&sx<=r&&sy<=c&&w[sx][sy]<w[x][y]){
            int tmp=ff(sx,sy)+1;
            if(tmp>t) t=tmp;
        }
    }
    dp[x][y]=t;
    return t;
}
int main(){
    while(scanf("%d %d",&r,&c)!=EOF){
        for(int i=1;i<=r;++i)
            for(int j=1;j<=c;++j)
            scanf("%d",&w[i][j]);
        memset(dp,0,sizeof(dp));
        int ans=0;
        for(int i=1;i<=r;++i)
        for(int j=1;j<=c;++j){
            dp[i][j]=ff(i,j);
            ans=max(ans,dp[i][j]);
        }
        printf("%d\n",ans);
    }
    return 0;
}

**饭卡 **

电子科大本部食堂的饭卡有一种很诡异的设计，即在购买之前判断余额。如果购买一个商品之前，卡上的剩余金额大于或等于5元，就一定可以购买成功（即使购买后卡上余额为负），否则无法购买（即使金额足够）。所以大家都希望尽量使卡上的余额最少。 
某天，食堂中有n种菜出售，每种菜可购买一次。已知每种菜的价格以及卡上的余额，问最少可使卡上的余额为多少。 

在讲述DP算法的时候，一个经典的例子就是数塔问题，它是这样描述的： 

有如下所示的数塔，要求从顶层走到底层，若每一步只能走到相邻的结点，则经过的结点的数字之和最大是多少？ 

已经告诉你了，这是个DP的题目，你能AC吗?