洛谷 P1541. [NOIP2010 提高组] 乌龟棋
原题链接
中等
作者:
y总的小迷弟
,
2023-07-28 21:48:07
,
所有人可见
,
阅读 77
//四维dp,其实思维上并没有那么难
#include<bits/stdc++.h>
using namespace std;
int n, m;
int na, nb, nc, nd;
int a[360];
int b[130];
int f[45][45][45][45];//f[i][j][k][p]表示用了四种卡片各用了i,j,k,p张
int main()
{
cin >> n >> m;
for(int i = 1;i <= n;i++)
cin >> a[i];
for(int i = 1;i <= m;i++)
{
cin >> b[i];
if(b[i] == 1)
na++;
if(b[i] == 2)
nb++;
if(b[i] == 3)
nc++;
if(b[i] == 4)
nd++;
//统计四种卡片张数
}
f[0][0][0][0] = a[1];//初始化,都选0张显然就是第一个格子的分数
for(int i = 0;i <= na;i++)
{
for(int j = 0;j <= nb;j++)
{
for(int k = 0;k <= nc;k++)
{
for(int p = 0;p <= nd;p++)
{
if(!(i == 0 && j == 0 && k == 0 && p == 0))//四个都为0,前面已经初始化过了,不需要更新
{
int t = -0x3f3f3f3f;
if(i != 0)
t = max(t, f[i - 1][j][k][p]);
if(j != 0)
t = max(t, f[i][j - 1][k][p]);
if(k != 0)
t = max(t, f[i][j][k - 1][p]);
if(p != 0)
t = max(t, f[i][j][k][p - 1]);
f[i][j][k][p] = t + a[1 + i + 2 * j + 3 * k + 4 * p];
//四种情况取个max再加本格子的分(a下标加1切记!!!)
}
}
}
}
}
cout << f[na][nb][nc][nd] << endl;//根据f数组的含义输出即可
return 0;
}