C++博客-生无所息

TJU_OI 1090 战地统计系统(War Field Statistical System)

Chen Jiecao — Sun, 26 Jul 2009 12:19:00 GMT

1090. 战地统计系统(War Field Statistical System)

输入文件名：c.in 输出文件名：c.out

提交讨论运行状况

2050年，人类与外星人之间的战争已趋于白热化。就在这时，人类发明出一种超级武器，这种武器能够同时对相邻的多个目标进行攻击。凡是防御力小于或等于这种武器攻击力的外星人遭到它的攻击，就会被消灭。然而，拥有超级武器是远远不够的，人们还需要一个战地统计系统时刻反馈外星人部队的信息。这个艰巨的任务落在你的身上。请你尽快设计出这样一套系统。

这套系统需要具备能够处理如下2类信息的能力：

1.外星人向[x1，x2]内的每个位置增援一支防御力为v的部队。

2.人类使用超级武器对[x1，x2]内的所有位置进行一次攻击力为v的打击。系统需要返回在这次攻击中被消灭的外星人个数。

注：防御力为i的外星人部队由i个外星人组成，其中第j个外星人的防御力为j。

输入格式

从文件c.in第一行读入n，m。其中n表示有n个位置，m表示有m条信息。

以下有m行，每行有4个整数k，x1，x2，v用来描述一条信息。k表示这条信息属于第k类。x1，x2，v为相应信息的参数。k=1 or 2。

注：你可以认为最初的所有位置都没有外星人存在。

规模：0

输出格式

结果输出到文件c.out。按顺序输出需要返回的信息。

输入样例

输出样例

6
9

样例说明

输入样例   对应输出     输出样例
3 5             无              6
1 1 3 4         无              9
2 1 2 3         6
1 1 2 2         无
1 2 3 1         无
2 2 3 5         9

题目来源 ：OIBH 信息学练习赛 #6

题目标签 ：

二维(1) 线段树(1)

这个题目的标签是二维+线段树,我估计有些哥们真的用二维线段树来做了,查看了一下后面的代码,发现大多数的人的代码都超过2k,有的还达到s四五k之多.
我的思路是把这个题目转化成矩形切割来做,x,y,v三个参数以及默认的一个初始值代表了一个矩形区域,左下角(x1,y1)=(x,1),右上角(x2,y2)=(y,v);
切割的大体方法是从USACO上的一个题目学来的,类似木块上浮,从第一个矩形一直浮到最上面的矩形,每碰到一个遮盖的矩形就分裂当前矩形,在上浮的过程中计算出每次询问的答案.
如果你对矩形切割很了解,相信我的代码还是比较容易理解的.

1 #include<iostream>
2 using namespace std;
3 const int MAXM=3000+100;
4 struct rect
5 {
6   int x1,y1,x2,y2;
7   rect(){};
8   rect(int x1,int y1,int x2,int y2) : x1(x1),y1(y1),x2(x2),y2(y2) {}
9 }temp,q[MAXM];
10
11 int pos[MAXM],cp=0,ans[MAXM],n,m;
12 bool mark[MAXM];
13
14 inline bool is_parted(rect& a,rect& b)
15 {
16   return (a.x2<b.x1 || a.x1>b.x2 || a.y2<b.y1 || a.y1>b.y2);
17 }
18
19 void Cut(int p,rect cur)
20 {
21   if (p>cp) return;
22   while ( p<=cp && is_parted(cur,q[pos[p]]) ) ++p;
23   if (p>cp) return;
24   rect ques=q[pos[p]];
25   int area=(cur.y2-cur.y1+1)*(cur.x2-cur.x1+1);
26   if (cur.x1<ques.x1){
27     area-=(ques.x1-cur.x1)*(cur.y2-cur.y1+1);
28     rect temp=cur;
29     cur.x1=ques.x1;
30     temp.x2=ques.x1-1;
31     Cut(p+1,temp);
32   }
33   if (cur.x2>ques.x2){
34     area-=(cur.x2-ques.x2)*(cur.y2-cur.y1+1);
35     rect temp=cur;
36     cur.x2=ques.x2;
37     temp.x1=ques.x2+1;
38     Cut(p+1,temp);
39   }
40   if (cur.y2>ques.y2){
41     area-=(cur.y2-ques.y2)*(cur.x2-cur.x1+1);
42     rect temp=cur;
43     cur.y2=ques.y2;
44     temp.y1=ques.y2+1;
45     Cut(p+1,temp);
46   }
47   if (cur.y1<ques.y1){
48     area-=(ques.y1-cur.y1)*(cur.x2-cur.x1+1);
49     rect temp=cur;
50     cur.y1=ques.y1;
51     temp.y2=ques.y1-1;
52     Cut(p+1,temp);
53   }
54   ans[p]+=area;
55 }
56
57 int main()
58 {
59   freopen("c.in","r",stdin);
60   freopen("c.out","w",stdout);
61   memset(mark,0,sizeof(mark));
62   cin >> n >> m;
63   for (int i=0;i<m;++i){
64     int k,x,y,v;
65     cin >> k >> x >> y >> v;
66     q[i]=rect(x,1,y,v);
67     if (k==2){
68       mark[i]=1;
69       pos[++cp]=i;
70     }
71   }
72
73   memset(ans,0,sizeof(ans));
74   int p=1;
75   for (int i=0;i<m;++i){
76     if (mark[i]) { ++p; continue; }
77     Cut(p,q[i]);
78   }
79   for (int i=1;i<=cp;++i) cout << ans[i] << endl;
80
81   return 0;
82 }
83

Chen Jiecao 2009-07-26 20:19 发表评论

TJU_OI 1140 箱里的钥匙

Chen Jiecao — Sun, 26 Jul 2009 04:43:00 GMT

1140. 箱里的钥匙

输入文名：box.in
输出文名：box.out

提交讨论运行状况

有N个编号为1到N的箱子和N个编号为1到N的钥匙，第i号钥匙只能用来打开第i号箱子。现在我们随机地将一把钥匙锁进一个箱子里，即每个箱子里都恰好有一把钥匙，保证所有的情况都等可能性地出现。现在你有M个炸弹，每个炸弹可以用来炸开一个箱子，一旦你把某个箱子打开，你就可以取出其中的钥匙，从而有可能用这钥匙打开更多的箱子。你的策略很简单，当没有箱子可以打开时，随便选一个箱子，用炸弹炸开它，取出钥匙并继续打开尽可能多的箱子，直至没有箱子可以打开，然后继续使用下一颗炸弹。

现给定N，你的任务是求出你可以取得所有钥匙的概率。这个概率必须输出成分数“A/B”的形式，A和B都是正整数且公约数必须为1。

输入格式

输入一行，包含空格隔开的两个数N和M

输出格式

输出为A/B的形式。

输入样例

3 1

输出样例

1/3

数据规模与约定

1 ≤ N ≤ 20, 1 ≤ M ≤ N

解析:
这个题目基本上就是一个数学题,涉及到第一类stirling数的求解.
所谓第一类stirling数,例如S[n,k]表示将一个大小为n的集合分成k个部分,每个部分的元素个数不小于1,且形成环的总方法数.
一个元素也算作单独的环.
容易的到
S[1,1]=1;
S[n,0]=0;
当n对合法的n,k,满足: S[n,k]=S[n-1,k-1]+(n-1)*S[n-1,k];
把n当作钥匙(也即箱子)的个数,k为钥匙所放位置形成的"环",每破坏一个箱子,都可以得到该箱子所属环的所有钥匙,k表示实际的环的个数
当k>m时便不可能取得到所有的钥匙.
这样下面的代码就很好理解了.

1 #include<iostream>
2 using namespace std;
3 const int MAXN=30;
4 template <class T>
5 T Gcd(T a,T b)
6 {
7   return (!a)? b : Gcd(b%a,a);
8 }
9
10 int main()
11 {
12   freopen("box.in","r",stdin);
13   freopen("box.out","w",stdout);
14   long long n,m,S[MAXN][MAXN];
15   cin >> n >> m;
16   memset(S,0,sizeof(S));
17   S[1][1]=1;
18   for (int i=2;i<=n;++i)
19     for (int j=1;j<=i;++j)
20       S[i][j]=S[i-1][j-1]+(i-1)*S[i-1][j];
21   long long B=1;
22   for (int i=2;i<=n;++i) B*=i;
23   long long A=B;
24   for (int i=m+1;i<=n;++i) A-=S[n][i];
25   long long G=Gcd(A,B);
26   cout << A/G << '/' << B/G << endl;
27   return 0;
28 }
29

Chen Jiecao 2009-07-26 12:43 发表评论

TJU_OI 1094 珍珠项链

Chen Jiecao — Wed, 22 Jul 2009 07:15:00 GMT

1094. 珍珠项链

输入文件名：necklace.in
输出文件名：necklace.out

提交讨论运行状况

有一串由n个珍珠组成的珍珠项链，珍珠的编号为1..n，每个珍珠都有各自的价值，我们用w[i]表示编号为i的珍珠的价值（注意：w[i]可以小于零），已知这n个珍珠的价值量总和是n-1,现要求你在项链的某个位置断开，使得断开后的珍珠链满足对于任意k,前k个珍珠的价值量总和不超过k-1. (对断开的一点说明, 如果在位置p断开, 那么得到的珍珠链将一定是p,p+1,...,n,1,2,...,p-1)

输入格式

输入文件的第一行有一个唯一的整数n,

接下来n个用空格和换行符隔开的整数分别表示w[1],w[2],...,w[n]

输出格式

如果无解请输出一行"Impossible"（不含引号）否则输出一个整数表示断开后的珍珠链第一个珍珠的编号

输入样例

5
1 1 1 1 0

输出样例

数据规模与约定

3≤n≤200,000 -1,000,000,000≤w[i]≤1,000,000,000

40%的测试数据满足n≤1,000

题目来源 ：OIBH 信息学练习赛 #8

代码:

1 #include<iostream>
2 using namespace std;
3 const int MAXN=200000+100;
4 long long n,w[MAXN<<1];
5 int main()
6 {
7   freopen("necklace.in","r",stdin);
8   freopen("necklace.out","w",stdout);
9   cin >> n;
10   for (int i=0;i<n;++i) cin >> w[i],w[i+n]=w[i];
11   long long len=0,tot=0;;
12   for (int i=0;i<n*2;++i)
13     {
14       if (tot+w[i]<=len) tot+=w[i],++len;
15       else
16     { tot=0; len=0; }
17       if (len==n) { cout << i-len+2 << endl; return 0; }
18     }
19   cout << "Impossible\n";
20   return 0;
21 }
22
23

基本上,就是枚举珍珠,如果某个珍珠可以作为第一颗珍珠,那么接着把它的下一颗当作第二颗,如果合法,继续下一颗,如果不合法,直接把当前不合法的这一颗的下一颗当作第一颗继续枚举.
为什么挡当前的这颗珍珠在这个位置不行,就不用在别的位置尝试呢?这是因为一旦某颗珍珠作为断掉之后的链第k颗不合法的话,它也一定不可能在当作第1、第2........或第k-1颗时合法,略证如下:
若A[1],A[2],A[3]......A[k-1] 作为前(k-1)颗珍珠合法................................................................................(1)
而A[1]+A[2]+A[3]+......+A[k]>k-1 不合法...........................................................................................(2)
那么我们有
A[t+1]+A[t+1]+......+A[k]>k-1-(A[1]+A[2]+......+A[t]) (1<=t(1)==> A[1]+A[2]+.......A[t]<=t-1
所以由(3)知 A[t+1]+A[t+2]+......A[k]>k-1-(t-1)=k-t...........................................................................(4)
而要想把A[t+1],A[t+2],.......A[k]当作第1,2,.........(k-t)颗珍珠且合法,必须有
A[t+1]+A[t+2]+.......A[k]<=k-t-1 (有k-t颗珠子)..................................................................................(5)
(4),(5)矛盾,所以红色部分得证.

Chen Jiecao 2009-07-22 15:15 发表评论

URAL 1022 Genealogical tree

Chen Jiecao — Tue, 21 Jul 2009 09:14:00 GMT

拓扑排序是最直接的算法.

1 /* 拓扑排序 */
2
3 #include<iostream>
4 #include<vector>
5 using namespace std;
6 const int MAXN=120;
7 vector<int> adj[MAXN];
8
9 int into[MAXN];
10
11 int main()
12 {
13   //freopen("data.in","r",stdin);
14   //freopen("data.out","w",stdout);
15   int n;
16   memset(into,0,sizeof(into));
17   cin >> n;
18   for (int i=1;i<=n;++i)
19     {
20       int x;
21       cin >> x;
22       while (x!=0)
23     {
24       adj[i].push_back(x);
25       ++into[x];
26       cin >> x;
27     }
28     }
29  //for (int i=1;i<=n;++i) cout << into[i] << ' '; cout << endl;
30   bool everp=0;
31   for (int k=0;k<n;++k)
32     {
33       int i=1;
34       for (;i<=n;i++) if (!into[i]) break;
35       (everp) ? cout << ' ' << i : cout << i;
36       everp=1;
37       --into[i];
38       for (int j=0;j<adj[i].size();++j) --into[ adj[i][j] ];
39     }
40   cout << endl;
41   return 0;
42 }
43

Chen Jiecao 2009-07-21 17:14 发表评论

URAL 1021 Sacrament of the sum

Chen Jiecao — Tue, 21 Jul 2009 09:12:00 GMT

水题,由于给出的已经是单调的序列,所以有o(N)的算法

1 #include<iostream>
2 using namespace std;
3 const int MAXN=50005;
4
5
6 int main()
7 {
8   freopen("data.in","r",stdin);
9   freopen("data.out","w",stdout);
10   int c,cc,num[MAXN];
11   cin >> c;
12   for (int i=0;i<c;++i) cin >> num[i];
13   num[c]=31440461;
14   cin >> cc;
15   int p=0;
16   for (int i=0;i<cc;++i)
17     {
18       int x;
19       cin >> x;
20       while (x+num[p]<10000) ++p;
21       if (x+num[p]==10000) { cout << "YES\n"; return 0; }
22     }
23   cout << "NO\n";
24   return 0;
25 }
26

Chen Jiecao 2009-07-21 17:12 发表评论

URAL 1020 Rope

Chen Jiecao — Mon, 20 Jul 2009 08:49:00 GMT

水题,没什么好说的,注意N=1的情况.

1 #include<iostream>
2 #include<math.h>
3 using namespace std;
4 const double PI=3.1415926;
5
6 template <class T>
7 T dis(T x1,T y1,T x2,T y2)
8 {
9   return sqrt( (x1-x2)*(x1-x2) + (y1-y2)*(y1-y2) );
10 }
11 int main()
12 {
13   int n;
14   double r,len=0;
15   //freopen("data.in","r",stdin);
16   //freopen("data.out","w",stdout);
17   cin >> n >> r;
18   double x0,y0,x,y;
19   cin >> x0 >> y0;
20   double px=x0,py=y0;
21 if (n==1) goto L1;
22   for (int i=1;i<n;++i)
23     {
24       cin >> x >> y;
25       len+=dis(px,py,x,y);
26       px=x;
27       py=y;
28     }
29   len+=dis(x,y,x0,y0);
30 L1:  len+= 2*PI*r ;
31   printf("%.2f\n",len);
32   return 0;
33 }
34

Chen Jiecao 2009-07-20 16:49 发表评论

URAL 1019 A line painting

Chen Jiecao — Mon, 20 Jul 2009 07:00:00 GMT

A Line painting

Time Limit: 2.0 second
Memory Limit: 16 MB

The segment of numerical axis from 0 to 10⁹ is painted into white color. After that some parts of this segment are painted into black, then some into white again and so on. In total there have been made N re-paintings (1 ≤ N ≤ 5000). You are to write a program that finds the longest white open interval after this sequence of re-paintings.

Input

The first line of input contains the only number N. Next N lines contain information about re-paintings. Each of these lines has a form:
a_i b_i c_i
where a_i and b_i are integers, c_i is symbol 'b' or 'w', a_i, b_i, c_i are separated by spaces.
This triple of parameters represents repainting of segment from a_i to b_i into color c_i ('w' — white, 'b' — black). You may assume that 0 < a_i < b_i < 10⁹.

Output

Output should contain two numbers x and y (x < y) divided by space(s). These numbers should define the longest white open interval. If there are more than one such an interval output should contain the one with the smallest x.

Sample

input	output
4 1 999999997 b 40 300 w 300 634 w 43 47 b	47 634

这个题目最直接的办法是离散化,离散化了之后就好折腾了,因为操作指令很少,所以我选择离散+朴素染色.
复杂度上界为O(M*M),这里M表示离散化后得到的区间个数.

1 #include<iostream>
2 #include<algorithm>
3 using namespace std;
4 const int MAXN=10005;
5 const int MAXL=1000000000;
6 struct re
7 {
8   int a,b;
9   char c;
10 }op[MAXN];
11
12 int n,p=0,que[MAXN];
13 bool color[MAXN<<1];
14
15 /* 二分查找 */
16 int find(int num)
17 {
18   int l=0,r=p+1,mid;
19   while (r-l>1)
20     {
21       mid=(l+r) >> 1;
22       (que[mid]<=num)? l=mid : r=mid;
23       if (que[l]==num) return l;
24     }
25   return l;
26 }
27
28 void disp(re& op)
29 {
30   /* 区间由1开始数,而不是由0开始 */
31   op.a=find(op.a)+1;
32   op.b=find(op.b);
33 }
34
35 void mark(int l,int r,char c)
36 {
37   for (int i=l;i<=r;++i) color[i]=(c=='b');
38 }
39
40 int main()
41 {
42  // freopen("data.in","r",stdin);
43  // freopen("data.out","w",stdout);
44   cin >> n;
45   for (int i=0;i<n;++i)
46     {
47       cin >> op[i].a >> op[i].b >> op[i].c;
48       que[++p]=op[i].a;
49       que[++p]=op[i].b;
50     }
51   que[++p]=MAXL;
52   /* 删除重复出现的数字 */
53   int rp=0;
54   for (int i=1;i<=p;++i)
55     if (que[rp]!=que[i]) que[++rp]=que[i];
56   p=rp;
57   /* 排序,便于定位和离散化 */
58   sort(que,que+p+1);
59   que[p+1]=MAXL+1;
60   /* 对操作进行离散处理 */
61   for (int i=0;i<n;++i) disp(op[i]);
62   /* 处理操作序列 */
63   memset(color,0,sizeof(color));
64   for (int i=0;i<n;++i) mark(op[i].a,op[i].b,op[i].c);
65   int t=1,a,b,mlen=0;
66   for (int i=2;i<=p+1;++i)
67     if (color[i]!=color[t] || i>p)
68       {
69     if ((!color[t]) && (que[i-1]-que[t-1]>mlen)) { a=que[t-1];b=que[i-1];mlen=que[i-1]-que[t-1];}
70     t=i;
71       }
72   cout << a << ' ' << b << endl;
73   //system("pause");
74   return 0;
75 }
76

个别目标远大的同学可能并不仅仅是想解决这个题目,这时候建议你使用离散化+线段树,复杂度会大大地降低

Chen Jiecao 2009-07-20 15:00 发表评论

URAL 1018 A Binary Apple Tree

Chen Jiecao — Sun, 19 Jul 2009 15:02:00 GMT

A Binary Apple Tree

Time Limit: 1.0 second
Memory Limit: 16 MB

Let's imagine how apple tree looks in binary computer world. You're right, it looks just like a binary tree, i.e. any biparous branch splits up to exactly two new branches. We will enumerate by natural numbers the root of binary apple tree, points of branching and the ends of twigs. This way we may distinguish different branches by their ending points. We will assume that root of tree always is numbered by 1 and all numbers used for enumerating are numbered in range from 1 to N, where N is the total number of all enumerated points. For instance in the picture below N is equal to 5. Here is an example of an enumerated tree with four branches:

As you may know it's not convenient to pick an apples from a tree when there are too much of branches. That's why some of them should be removed from a tree. But you are interested in removing branches in the way of minimal loss of apples. So your are given amounts of apples on a branches and amount of branches that should be preserved. Your task is to determine how many apples can remain on a tree after removing of excessive branches.

Input

First line of input contains two numbers: N and Q (1 ≤ Q ≤ N; 1 < N ≤ 100). N denotes the number of enumerated points in a tree. Q denotes amount of branches that should be preserved. Next N−1 lines contains descriptions of branches. Each description consists of a three integer numbers divided by spaces. The first two of them define branch by it's ending points. The third number defines the number of apples on this branch. You may assume that no branch contains more than 30000 apples.

Output

Output should contain the only number — amount of apples that can be preserved. And don't forget to preserve tree's root ;-)

Sample

input	output
5 2 1 3 1 1 4 10 2 3 20 3 5 20	21

简析:
      这是一个简单的树形动态规划问题,大概可以拿来当这类题目的入门训练题.虽然这是URAL上的第一个树形DP,但是我奇怪的是它的通过率并不很高.
      对于原题目的图形,用数组value[a][b]表示a,b点间苹果的个数,用nd[p].L,nd[p].R分别表示节点p的左右儿子.通过build_tree(1)获得数组nd[],从而获得整棵树的信息.
接着,用ans[p][i]表示以节点p为祖宗的子树,保留的枝条不超过i条时所能保留的最多的苹果,状态转移有一下几种情况.
在除去多余枝条的后的图中,
1. p只与一个儿子相连:
    ans[p][i]=max(ans[left_son][i-1]+value[left_son][p],ans[right_son][i-1]+value[right_son][p]);
2. p与两个儿子相连:
    for (int j=0;j<=i-2;++j)
      ans[p][i]=max(ans[p][i],ans[left_son][j]+ans[right_son][i-j-2]+d);
    这里,d=value[left_son][p]+value[right_son][p];

算法在o(N*Q*Q)级别

1 #include<iostream>
2 using namespace std;
3 const int MAXN=102;
4 int n,q,value[MAXN][MAXN],ans[MAXN][MAXN];
5 struct node
6 {
7   int l,r;
8 }nd[MAXN];
9
10 void build_tree(int p)
11 {
12   int flg=0;
13   for (int i=1;i<=n;++i)
14     if (value[p][i] && (!nd[i].l))
15       {
16     flg=1;
17     if (nd[p].l==0) nd[p].l=i;
18     else
19       {nd[p].r=i; break;}
20       }
21   if (!flg) return;
22   if (nd[p].l) build_tree(nd[p].l);
23   if (nd[p].r) build_tree(nd[p].r);
24 }
25
26 void calc(int p)
27 {
28   if (!nd[p].l) return;
29   int l=nd[p].l,r=nd[p].r;
30   calc(l);
31   calc(r);
32   ans[p][1]=max(value[l][p],value[r][p]);
33
34   int d=value[l][p]+value[r][p];
35   for (int i=2;i<=q;++i)
36   {
37     ans[p][i]=max(ans[l][i-1]+value[l][p],ans[r][i-1]+value[r][p]);
38     for (int j=0;j<=i-2;++j)
39       ans[p][i]=max(ans[p][i],ans[l][j]+ans[r][i-j-2]+d);
40   }
41 }
42
43
44 int main()
45 {
46   //freopen("data.in","r",stdin);
47   //freopen("data.out","w",stdout);
48   cin >> n >> q;
49   memset(value,0,sizeof(value));
50   for (int i=1;i<n;++i)
51     {
52       int a,b,c;
53       cin >> a >> b >> c;
54       value[a][b]=c;
55       value[b][a]=c;
56     }
57   memset(nd,0,sizeof(nd));
58   build_tree(1);
59   calc(1);
60   cout << ans[1][q] << endl;
61   return 0;
62 }
63

Chen Jiecao 2009-07-19 23:02 发表评论

没有写下去的欲望了

Chen Jiecao — Sat, 18 Jul 2009 08:38:00 GMT

       C++,写写OI的东西现在是够了,也看了一些书,比如 Essential C++, Accelerate C++,我的目的倒也不是想达到什么高度,像Template,基本能用就行,类也只要有点概念,能看懂就够了.而在USACO上做这些已经做过的题目多少显得乏味,再者,由于脑子里留着对原来算法的印象,我的潜意识总是引导我直接默写.这样的coding绝对算不上一种享受.
      所以我打算挑几个题目做做,而不必机械式地重复,也可以去USACO上找些历次月赛的题目,金牌组的那些还是有点意思的,很多要求对高级数据结构进行改造,我以前做了几个题目,感觉收获极丰富,银牌组的也还比较有趣.
      我的耐性真的不怎么样,Vijos上做了99题,TJU的网站上做了几十题,URAL上做了几十题,PKU做过一点,SPOJ也玩过一下,连郭佳宝同志的OJ上也切了一些题目,花样很多,可是没有一个题库上一百题的,耐性不够,也是程序员的大忌.
     所谓USACO,重走长征路,看来是要当逃兵了,或者,算是踩高跷,Accelerate?

Chen Jiecao 2009-07-18 16:38 发表评论

USACO 1.5.1 Number Triangles

Chen Jiecao — Fri, 17 Jul 2009 03:18:00 GMT

这个题目,或者说这样的题目是动态规划的入门例题.这里的最优结构很明显,算法上没有什么好讲的.实现上,建议利用滚动数组以节省空间,虽然你开个二维的也未必会挤爆空间.

1 /*
2 ID: 31440461
3 LANG: C++
4 TASK: numtri
5 */
6 #include<iostream>
7 using namespace std;
8 const int MAXN=1000+10;
9 int data[2][MAXN];
10
11 int main()
12 {
13   freopen("numtri.in","r",stdin);
14   freopen("numtri.out","w",stdout);
15   int n,flg=0;
16   cin >> n;
17   for (int i=1;i<=n;++i)
18     {
19       flg=1-flg;
20       for (int j=1;j<=i;++j)
21     {
22       int x;
23       cin >> x;
24       data[flg][j]=max(data[!flg][j-1],data[!flg][j])+x;
25     }
26     }
27   int m=0;
28   for (int i=1;i<=n;++i) m=max(m,data[flg][i]);
29   cout << m << endl;
30   return 0;
31 }
32

Chen Jiecao 2009-07-17 11:18 发表评论