P1541 乌龟棋
题目描述
乌龟棋的棋盘是一行
乌龟棋中
游戏中,乌龟棋子自动获得起点格子的分数,并且在后续的爬行中每到达一个格子,就得到该格子相应的分数。玩家最终游戏得分就是乌龟棋子从起点到终点过程中到过的所有格子的分数总和。
很明显,用不同的爬行卡片使用顺序会使得最终游戏的得分不同,你能告诉小明,他最多能得到多少分吗?
输入格式
每行中两个数之间用一个空格隔开。
第
第
第
输入数据保证到达终点时刚好用光
输出格式
一个整数,表示小明最多能得到的分数。
Solution
多维 DP
int f[45][45][45][45];
void solve() {
int n, m;cin >> n >> m;
vector<int> a(n + 1), b(n + 1);
for (int i = 1;i <= n;i++)cin >> a[i];
int num[5] = {};
for (int i = 1;i <= m;i++) {
int x;cin >> x;num[x]++;
}
f[0][0][0][0] = a[1];
for (int i = 0;i <= num[1];i++) {
for (int j = 0;j <= num[2];j++) {
for (int k = 0;k <= num[3];k++) {
for (int p = 0;p <= num[4];p++) {
int r = 1 + i + 2 * j + 3 * k + 4 * p;
if (i)f[i][j][k][p] = max(f[i][j][k][p], f[i - 1][j][k][p] + a[r]);
if (j)f[i][j][k][p] = max(f[i][j][k][p], f[i][j - 1][k][p] + a[r]);
if (k)f[i][j][k][p] = max(f[i][j][k][p], f[i][j][k - 1][p] + a[r]);
if (p)f[i][j][k][p] = max(f[i][j][k][p], f[i][j][k][p - 1] + a[r]);
}
}
}
}
cout << f[num[1]][num[2]][num[3]][num[4]] << '\n';
}