首页 > 代码库 > HDU 1176 DP

HDU 1176 DP

2024-08-09 19:14:27   216人阅读

题目大意:

在0~10这11个点上面接饼 ， 每秒最多往左或往移动一格，或者保持原地不动

 

令dp[i][j]表示在第 i 秒在 第 j 个点上最多能得到的饼的数量

dp[i][j] = max(dp[i-1][j] , dp[i-1][j-1] , dp[i-1][j+1]) + a[i][j]  //a[i][j]在 i 时刻第 j 个位置会掉下来的饼的数量，如果没有置为0

 

这里要注意的一点是，最初从 5 号点出发，我们需要考虑到后面即使有饼因为根本无法走到那个位置，因而拿不到饼的情况

 

 1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4  5 using namespace std; 6 const int TIME = 100005; 7  8 int dp[TIME][12] , vis[12] , a[TIME][12]; 9 10 11 int main()12 {13     int n , x , t , time;14     while(scanf("%d" , &n) , n)15     {16         time = 0;17         memset(a , 0 , sizeof(a));18         for(int i = 0 ; i<n ; i++){19             scanf("%d%d" , &x , &t);20             time = max(time , t);21             a[t][x]++;22         }23 24         memset(dp , -1 , sizeof(dp));25         dp[0][5] = 0;//表示在第0秒只有5号点可到达的，其他不可达的点均为-126         for(int i = 1 ; i<=time ; i++){27             //动态规划更新第time时间的11个点的位置能达到的最优的dp值28             if(dp[i-1][0] >= 0 || dp[i-1][1] >= 0)29                 dp[i][0] = max(dp[i-1][0] , dp[i-1][1]) + a[i][0];30 31             for(int j = 1 ; j<10 ; j++){32                 if(dp[i-1][j-1] >= 0 || dp[i-1][j] >= 0 || dp[i-1][j+1] >=0)33                     dp[i][j] = max(dp[i-1][j] , max(dp[i-1][j-1] , dp[i-1][j+1])) + a[i][j];34             }35             if(dp[i-1][10] >= 0 || dp[i-1][9] >= 0)36                 dp[i][10] = max(dp[i-1][10] , dp[i-1][9]) + a[i][10];37 38             /*for(int j = 0 ; j<=10 ; j++)39                 printf("%-4d" , dp[i][j]);40             printf("\n");*/41         }42 43         int maxn = 0;44         for(int i = 0 ; i<=10 ; i++)45             maxn = max(maxn , dp[time][i]);46         printf("%d\n" , maxn);47     }48     return 0;49 }

 

HDU 1176 DP


联系
我们