HDU 1422 重温世界杯（DP）

题意：中文题不详述。

思路：根据题目描述及样例可以看出来，如果你第一个城市选的是生活费减花费大于等于0的时候才可以，最好是多余的，这样接下来的就算是花超了（一定限度内的花超），也可以通过前边的剩余来补充进去，就可以多玩一个。所以先存一下每个城市的生活费减去花费的剩余，然后从非负开始找，找一个数组存一下现在还剩下的多余花费，还要在找一个数组存一下当前点用的天数，可以从头开始重新选择新的城市。

 //HDU 1422

 #include <stdio.h>

 #include <string.h>

 #include <iostream>

 using namespace std;

 int a[] ;

 int c[] ;

 int sum[] ;

 int main()

 {

     int n;

     while(~scanf("%d",&n))

     {

         int w, l ;

         for(int i =  ; i < n ; i++)

         {

             scanf("%d %d",&w,&l) ;

             a[i] = a[n+i] = w-l ;

         }

         int i ;

         for(i =  ; i < *n ; i++)

             if(a[i] >= )

                 break ;

         if(i == *n)

         {

             printf("0\n") ;

             continue;

         }

         int cnt =  ;

         sum[i] = a[i] ;

         c[i] =  ;

         i++ ;

         for( ; i < *n ; i++)

         {

             if(cnt == n) break ;

             if(sum[i-] + a[i] >= )

             {

                 c[i] = c[i-]+ ;

                 sum[i] = sum[i-]+a[i] ;

                 cnt = max(cnt,c[i]) ;

             }

             else

             {

                 sum[i] =  ;

                 c[i] =  ;

             }

         }

         printf("%d\n",cnt) ;

     }

     return  ;

 }

巴特西

HDU 1422 重温世界杯（DP）

最新文章

热门文章