锐客网

  1. 首页 > 睿知 > it技术 > >

poj2385 Apple Catching（dp状态转移方程推导）

IT知识转移推导状态转移

青春须早为，岂能长少年。这篇文章主要讲述poj2385 Apple Catching（dp状态转移方程推导）相关的知识，希望能为你提供帮助。
https://vjudge.net/problem/POJ-2385
【poj2385 Apple Catching（dp状态转移方程推导）】猛刷简单dp的第一天的第一题。
状态：dp[i][j]表示第i秒移动j次所得的最大苹果数。关键要想到移动j次，根据j的奇偶判断人在哪里。
想了挺久的，最后还是参考了一篇和自己思路最近的代码https://blog.csdn.net/hellohelloc/article/details/52050207
我比他缺少的是特判dp[i][0]的状态，后面的一切都以此为基础的。

1 #include< iostream> 2 #include< cstdio> 3 #include< queue> 4 #include< cstring> 5 #include< algorithm> 6 #include< cmath> 7 #include< set> 8 #define INF 0x3f3f3f3f 9 typedef long long ll; 10 using namespace std; 11 int a[1010], dp[1010][1010]; 12 int main() 13 { 14memset(dp, 0, sizeof(dp)); 15int n, m; 16cin > > n > > m; 17for(int i = 1; i < = n; i++){ 18cin > > a[i]; 19} 20for(int i = 1; i < = n; i++){ 21dp[i][0] = dp[i-1][0]; 22if(a[i] == 1){//苹果在左边 23dp[i][0]++; 24for(int j = 1; j < = m; j++){ 25if(j& 1)//人在右边 26dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]); 27else//人在左边 28dp[i][j] = max(dp[i-1][j], dp[i-1][j-1])+1; 29} 30} 31else{//苹果在右边 32for(int j = 1; j < = m; j++){ 33if(j& 1)//人在右边 34dp[i][j] = max(dp[i-1][j], dp[i-1][j-1])+1; 35else//人在左边 36dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]); 37} 38} 39} 40int maxm = -INF; 41for(int i = 0; i < = m; i++){ 42maxm = max(maxm, dp[n][i]); 43} 44cout < < maxm < < endl; 45return 0; 46 }

 

    推荐阅读


    上一篇：flask 学习app代码备份

    下一篇：Android中的动态字符串的处理