思路:
f[i][j] 为第i分钟奶牛移动了j次接到苹果的最大值;
则f[i][j]=max(f[i-1][j],f[i-1][j-1]),同时要加上此时在当前接到的苹果数,即加一
ACcode:
#include<bits/stdc++.h>
using namespace std;
#define int long long
int t,w,w1,w2,ans,f[1005][35],a[1005];//在1~i时间内移动的次数获得的最多数量
void solve() {
cin>>t>>w;
for(int i=1; i<=t; i++) cin>>a[i];
for(int i=1; i<=t; i++) { //第几分钟
f[i][0]=f[i-1][0];
if(a[i]==1) f[i][0]++;
for(int j=1; j<=w; j++) { //转移了几次
if(j%2+1==a[i]) w1=1,w2=0;//移动j次后在第一颗树
else w1=0,w2=1;//移动j次后在对面树
f[i][j]=max(f[i-1][j]+w1,f[i-1][j-1]+w2);
}
}
for(int i=0; i<=w; i++) {
ans=max(ans,f[t][i]);
}
cout<<ans<<"\n";
}
signed main() {
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int tt=1;
//cin>>tt;
while(tt--)
solve();
return 0;
}
记忆化搜索:文章来源:https://www.toymoban.com/news/detail-617278.html
#include <cstdio> //头文件
#include <iostream>
#include <cstring>
using namespace std;
int n, w, a[1005], f[1005][3][35]; //三维数组f表状态
int dfs(int i,int j,int k) //i为时间点,j为哪棵树,k为移动了多少次
{
if (i > n)return 0; //边界条件
if (f[i][j][k] != -1)return f[i][j][k]; //如果搜过了就直接返回
int tmp1 = 0, tmp2 = 0; //tmp1(2)表示决策1(2)的答案
if (k < w && a[i] != j) //决策1(移动到另一棵树),这里有个小剪枝:如果在这个时间点里,当前位置会有果子落下,就不走
tmp1 = dfs(i + 1, -1 * j + 3, k + 1) + 1; //-1 * j + 3这里表示移动,你可以把1,2代进去算一下
tmp2 = dfs(i + 1, j, k) + (j == a[i] ? 1 : 0); //决策2(不动),如果有果子落下就+1。ps:判断语句一定要加括号,我就是因为这个WA
return f[i][j][k] = max(tmp1, tmp2); //返回接到果子多的决策
}
int main()
{
//freopen(" .in","r",stdin); //在此提醒广大noip考生,一定要加文件输入输出
//freopen(" .out","w",stdout);
cin >> n >> w;
for (int i = 1; i <= n; i++)
cin >> a[i];
memset(f, -1, sizeof(f)); //把f数组赋值为-1,头文件<cstring>
cout << dfs(1, 1, 0); //开始爆搜
}
over~文章来源地址https://www.toymoban.com/news/detail-617278.html
到了这里,关于【洛谷】P2690 [USACO04NOV] Apple Catching G(dp or 记忆化搜索)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!