Hdu1422 revisits the world cup [DP]

Topic link ：

​ ​http://acm.hdu.edu.cn/showproblem.php?pid=1422​​

The main idea of the topic ：

Here you are. N Cities , The tour route is 1~2~3~4~5~…~N~1. You can start from any city . Every city offers

The cost of living and the expenses required are different , ask ： How many cities can you visit at most .

Ideas ：

Because it can form a cycle , So connect it after the original data 1~N The data of . Then use dynamic programming to do . Status as ： Become one

The remaining money in the city is not negative ( That is, the tour is not over yet ), If the money left in the previous city plus the money in the current city is greater than the current life

fee , that dp[i] = dp[i-1] + 1, Update the remaining money , If not enough travel , Just classify the rest of the money as 0, Starting from the current point

tourism , Calculate the biggest dp[i], What you get is the number of cities you can visit at most . Add an optimization here , When dp[i] == N( After visiting

N Cities ) When , Out of the loop .

AC Code ：

Log in and copy

      
      

       
       #include<iostream>
       
       

       
       #include<algorithm>
       
       

       
       #include<cstdio>
       
       

       
       #include<cstring>
       
       

       
       using 
       
       namespace 
       
       std;
       
       

       
       const 
       
       int 
       
       MAXN 
       
       = 
       
       200010;
       
       

       
       

       
       int 
       
       W[
       
       MAXN],
       
       L[
       
       MAXN],
       
       dp[
       
       MAXN];
       
       

       
       

       
       int 
       
       main()
       
       
{
       
       
    
       
       int 
       
       N,
       
       i;
       
       
    
       
       while(
       
       ~scanf(
       
       "%d",
       
       &
       
       N))
       
       
    {
       
       
        
       
       dp[
       
       0] 
       
       = 
       
       0;
       
       
        
       
       for(
       
       i 
       
       = 
       
       1; 
       
       i 
       
       <= 
       
       N; 
       
       ++
       
       i)
       
       
        {
       
       
            
       
       
            
       
       scanf(
       
       "%d %d",
       
       &
       
       W[
       
       i],
       
       &
       
       L[
       
       i]);
       
       
            
       
       W[
       
       i
       
       +
       
       N] 
       
       = 
       
       W[
       
       i];
       
       
            
       
       L[
       
       i
       
       +
       
       N] 
       
       = 
       
       L[
       
       i];
       
       
            
       
       dp[
       
       i] 
       
       = 
       
       dp[
       
       N
       
       +
       
       i] 
       
       = 
       
       0;
       
       
        }
       
       
        
       
       int 
       
       cost 
       
       = 
       
       0, 
       
       Max 
       
       = 
       
       0;
       
       
        
       
       for(
       
       i 
       
       = 
       
       1; 
       
       i 
       
       <= 
       
       2
       
       *
       
       N; 
       
       ++
       
       i)
       
       
        {
       
       
            
       
       if(
       
       cost 
       
       + 
       
       W[
       
       i] 
       
       >= 
       
       L[
       
       i])
       
       
            {
       
       
                
       
       dp[
       
       i] 
       
       = 
       
       dp[
       
       i
       
       -
       
       1] 
       
       + 
       
       1;
       
       
                
       
       cost 
       
       = 
       
       cost 
       
       + 
       
       W[
       
       i] 
       
       - 
       
       L[
       
       i];
       
       
            }
       
       
            
       
       else
       
       
                
       
       cost 
       
       = 
       
       0;
       
       
            
       
       if(
       
       dp[
       
       i] 
       
       > 
       
       Max)
       
       
                
       
       Max 
       
       = 
       
       dp[
       
       i];
       
       
            
       
       if(
       
       dp[
       
       i] 
       
       == 
       
       N)
       
       
                
       
       break;
       
       
        }
       
       
        
       
       
        
       
       printf(
       
       "%d\n",
       
       Max);
       
       
    }
       
       

       
       
    
       
       return 
       
       0;
       
       
}
      
      
      
      

       
       
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.
       
       
43.
       
       
44.