锐客网

  1. 首页 > it技术 > >

POJ|POJ 2385(Apple Catching)

链接：https://vjudge.net/problem/POJ-2385#author=SCU2018
思路：dp题，首先找到状态转移关系，有dp[i][j] = max(dp[i-1][j],dp[i-1][j-1])，如果此时所在位置还有苹果，那么dp[i][j]还需+1，注意最后输出的不一定是dp[t][m]，因为可能最大移动步数不需要用完，所以还需要dp[t][k]中寻找最大值。
【POJ|POJ 2385(Apple Catching)】代码：

#include #include #include using namespace std; int a[1001]; int dp[1001][31]; int main(){ memset(dp,0,sizeof(dp)); int t,m; cin>>t>>m; for(int i=1; i<=t; i++){ cin>>a[i]; } for(int i=1; i<=t; i++){ for(int j=0; j<=m; j++){ if(j==0)dp[i][j] = dp[i-1][j]; else dp[i][j] = max(dp[i-1][j],dp[i-1][j-1]); if(j%2+1==a[i])dp[i][j]++; } } int ans = dp[t][0]; for(int j=1; j<=m; j++){ ans = max(ans,dp[t][j]); } cout<

    推荐阅读


    上一篇：使用react-router-dom做移动端路由|使用react-router-dom做移动端路由 2019-08-12

    下一篇：《美得冒泡的幸福》写后感