生活随笔
收集整理的這篇文章主要介紹了
poj 3920(简单dp)
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
題意：從起點每次最多跳s步，最多跳t次，從起點到終點的最大得分。
解題思路：dp[i][j]表示第i次跳到位置j的最大得分。簡單的動態規劃。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;const int maxn = 205;
const int inf = 0x7ffffff;
int n,s,t;
int grid[maxn],dp[maxn][maxn];int main()
{while(scanf("%d",&n)!=EOF){if(n == 0) break;scanf("%d%d",&s,&t);for(int i = 0; i <= t; i++)for(int j = 0; j <= n+1; j++)dp[i][j] = -inf;memset(grid,0,sizeof(grid));for(int i = 1; i <= n; i++)scanf("%d",&grid[i]);for(int i = 1; i <= s; i++)dp[1][i] = grid[i];for(int i = 1; i < t; i++)for(int j = 1; j <= n; j++){if(dp[i][j] == -1) continue;for(int k = 1; k <= s; k++){int len = j + k; if(len > n) len = n + 1;dp[i+1][len] = max(dp[i+1][len],dp[i][j] + grid[len]);}}int ans = -inf;for(int i = 1; i <= t; i++)ans = max(ans,dp[i][n+1]);printf("%d\n",ans);}return 0;
}
總結
以上是生活随笔為你收集整理的poj 3920(简单dp)的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
