HDU 1422 重温世界杯 DP题

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1422

解题报告：DP题，要使旅行的城市最多，关键是要选出一个城市作为开始，以这个城市作为开始的城市时，能使拥有的钱能旅行的城市最多，我的做法是把前n-1个城市添加到n个城市的数组后面，这样就不用考虑环的问题了，

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 using namespace std;
 5 
 6 int w[200005],l[2000005];
 7 
 8 int main()
 9 {
10     int n;
11     while(scanf("%d",&n)!=EOF)
12     {
13         for(int i = 0;i<n;++i)
14         scanf("%d%d",&w[i],&l[i]);
15         for(int i = 0;i<n-1;++i)
16         w[i+n] = w[i],l[i+n] = l[i];
17         int temp = 0,tot = 0,flag = 0,M = 0; 
18         for(int i = 0;i<2*n-1;++i)
19         {
20             if(temp + w[i] - l[i] >= 0)
21             {
22                 tot ++;
23                 temp = temp + w[i] - l[i];
24             }
25             else
26             {
27                 if(tot <= n)
28                 M = max(tot,M);
29                 else
30                 {
31                     M = n;
32                     break;
33                 }
34                 temp = 0 ;
35                 tot = 0 ;
36             }
37         }
38         if(tot <= n)
39         M = max(tot,M);
40         else M = n;
41         printf("%d
",M);
42     }
43     return 0;
44 }
45

View Code