C++动态规划——经典题目（下）

上一篇文章没有写全，这篇再补两道题

酒鬼

#include<bits/stdc++.h>
using namespace std;
int dp[110][10]={0};
int a[1010]={0};
int n,m;
int main()
{cin>>n;dp[0][0]=0;dp[1][0]=0;dp[1][1]=a[1];for(int i=1;i<=n;i++){cin>>a[i];}for(int i=2;i<=n;i++){//不喝这瓶dp[i][0]=max(dp[i-1][0],max(dp[i-1][1],dp[i-1][2]));//喝这瓶，上一瓶没喝//dp[i][1]=a[i]+max(dp[i-2][0],max(dp[i-2][1],dp[i-2][2]));//因为上一瓶没喝，所以就等于dp[上一瓶][这瓶没喝]也就是dp[i-1][0]dp[i][1]=a[i]+dp[i-1][0];//喝这瓶，而且上一瓶也喝//dp[i][2]=a[i]+a[i-1]+max(dp[i-3][0],max(dp[i-3][1],dp[i-3][2]));//因为上一瓶喝过了，所以就等于dp[上瓶][喝这瓶]也就是dp[i-1][1]dp[i][2]=a[i]+dp[i-1][1];//不能再喝了，再喝就超过3瓶了，会不符合题意}cout<<max(dp[n][0],max(dp[n][1],dp[n][2]))+1;return 0;
}

奶牛散步

这里做一个解释，题目最后一句话里的“模12345”指的就是结果对12345取余（%12345）

#include<bits/stdc++.h>
using namespace std;
int _up[1010]={0};
int _right[1010]={0};
int _left[1010]={0};
int n,m;
int main()
{cin>>n;_up[1]=1;_right[1]=1;_left[1]=1;for(int i=2;i<=n;i++){//如果要这一步往上走，那么前一步从下面右边左边来都可以_up[i]=(_up[i-1]+_left[i-1]+_right[i-1])%12345;//如果这一步要往左走，那么只能从下面和右边来_left[i]=(_up[i-1]+_left[i-1])%12345;//如果这一步要往右走，那么只能从下面和左边来_right[i]=(_up[i-1]+_right[i-1])%12345;}cout<<(_up[n]+_right[n]+_left[n])%12345;return 0;
}