#动态规划，多重背包#codevs 1068 洛谷 1541 jzoj 1863 乌龟棋

本文主要是介绍#动态规划，多重背包#codevs 1068 洛谷 1541 jzoj 1863 乌龟棋，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

求通过走卡片的步数获得的最大得分（一开始在1，自动加上得分）

---

分析

长得挺像背包的，比较简单233

		int now=1+i+j*2+k*3+p*4;if (i) f[i][j][k][p]=max(f[i][j][k][p],f[i-1][j][k][p]+a[now]);if (j) f[i][j][k][p]=max(f[i][j][k][p],f[i][j-1][k][p]+a[now]);if (k) f[i][j][k][p]=max(f[i][j][k][p],f[i][j][k-1][p]+a[now]);if (p) f[i][j][k][p]=max(f[i][j][k][p],f[i][j][k][p-1]+a[now]);

---

代码

#include <cstdio>
#include <cctype>
#define max(a,b) (a>b)?a:b
using namespace std;
typedef unsigned short ust;
ust n,m,a[351],num[4],f[41][41][41][41];
ust in(){ust ans=0; char c=getchar();while (!isdigit(c)) c=getchar();while (isdigit(c)) ans=ans*10+c-48,c=getchar();return ans;
}
int main(){n=in(); m=in();for (int i=1;i<=n;i++) a[i]=in(); for (int i=1;i<=m;i++) num[in()-1]++;f[0][0][0][0]=a[1];for (int i=0;i<=num[0];i++)for (int j=0;j<=num[1];j++)for (int k=0;k<=num[2];k++)for (int p=0;p<=num[3];p++){int now=1+i+j*2+k*3+p*4;if (i) f[i][j][k][p]=max(f[i][j][k][p],f[i-1][j][k][p]+a[now]);if (j) f[i][j][k][p]=max(f[i][j][k][p],f[i][j-1][k][p]+a[now]);if (k) f[i][j][k][p]=max(f[i][j][k][p],f[i][j][k-1][p]+a[now]);if (p) f[i][j][k][p]=max(f[i][j][k][p],f[i][j][k][p-1]+a[now]);}return !printf("%d",f[num[0]][num[1]][num[2]][num[3]]);
}

这篇关于#动态规划，多重背包#codevs 1068 洛谷 1541 jzoj 1863 乌龟棋的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---