免費餡餅

? HDU - 1176?

這也是一道比較簡單的動態(tài)規(guī)劃

dp[i][j]表示到時間i，位置為j所能采集的最大餡餅數(shù)量

狀態(tài)轉(zhuǎn)移非常好寫

dp[i][j] = max{dp[i-1][j],dp[i-1][j-1],dp[i-1][j+1]} + T[j][i]

其中T[j][i]表示的是時間為i，位置為j落下的餡餅的數(shù)量

#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int MAX = 100000; const int INF = 1e9; int dp[MAX][14]; int T[14][MAX]; int main(){int n;while(~scanf("%d",&n) && n){for(int i = 0;i < MAX;i++){for(int j = 0;j <= 10;j++){dp[i][j] = -INF;}}memset(T,0,sizeof(T));int mx = 0;for(int i = 0;i < n;i++){int a,b;scanf("%d%d",&a,&b);T[a][b] ++;mx = max(mx,b);}dp[0][5] = 0;for(int i = 1;i <= mx;i++){for(int j = 0;j <= 10;j++){dp[i][j] = max(dp[i][j],dp[i-1][j-1] + T[j][i]);dp[i][j] = max(dp[i][j],dp[i-1][j] + T[j][i]);dp[i][j] = max(dp[i][j],dp[i-1][j+1] + T[j][i]);}}int ans = 0;for(int i = 0;i <= 10;i++){ans = max(ans,dp[mx][i]);}printf("%d\n",ans);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的动态规划训练18 [免费馅饼 HDU - 1176 ]的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。