题解 P1541 【乌龟棋】
小黑AWM
2019-07-11 23:46:15
## 简单线性DP
***
首先观察状态的设计，不难发现我们并不关心具体出的是第几张牌，而只关注我们现在出了哪些牌或者有哪些牌，再根据数据范围给出的提示（总共只有4种牌，每种牌的张数不超过40）这几乎是明示状态是什么了，我们在阶段划分时应该会用到步数，先把它也写进状态再说吧。
那么我们就得到了状态
$$f[n][w_1][w_2][w_3][w_4]$$
表示到第 $n$ 格我们每种牌还剩 $w_i$ 张时的最大分数，由于当前这个只能由 $i-1, i-2,i-3,i-4$ 转移过来，那么转移方程也是显然的了
$$f[i][w_1][w_2][w_3][w_4] = a[i] + max_{1≤k≤4}\{f[i-k][w_1+1][w_2][w_3][w_4]\}$$
$k$ 是几就把 $w_k+1$ 不一定是 $w_1$ 但因为公式太长写不下了。
无脑code:
```cpp
/*
* Author: xiaohei_AWM
* Date: 7.11
* Mutto: Face to the weakness, expect for the strength.
*/
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<ctime>
#include<utility>
#include<functional>
#include<cmath>
#include<vector>
#include<assert.h>
using namespace std;
#define reg register
#define endfile fclose(stdin);fclose(stdout);
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef std::pair<int,int> pii;
typedef std::pair<ll,ll> pll;
namespace IO{
char buf[1<<15],*S,*T;
inline char gc(){
if (S==T){
T=(S=buf)+fread(buf,1,1<<15,stdin);
if (S==T)return EOF;
}
return *S++;
}
inline int read(){
reg int x;reg bool f;reg char c;
for(f=0;(c=gc())<'0'||c>'9';f=c=='-');
for(x=c^'0';(c=gc())>='0'&&c<='9';x=(x<<3)+(x<<1)+(c^'0'));
return f?-x:x;
}
inline ll readll(){
reg ll x;reg bool f;reg char c;
for(f=0;(c=gc())<'0'||c>'9';f=c=='-');
for(x=c^'0';(c=gc())>='0'&&c<='9';x=(x<<3)+(x<<1)+(c^'0'));
return f?-x:x;
}
}
using namespace IO;
const int maxn = 351, maxm = 121;
int n, m, a[maxn], b[maxm], f[maxn][21][21][21][21];//f[i][w][x][y][z]表示到第i格，每种卡片分别还有 w x y z张的最大分值
int cnt[5], ans;
int main(){
n = read(), m = read();
for(int i = 1; i <= n; i++) a[i] = read();
for(int i = 1; i <= m; i++) b[i] = read(), cnt[b[i]]++;
f[1][cnt[1]][cnt[2]][cnt[3]][cnt[4]] = a[1];
int t[5];
for(int i = 2; i <= n; i++)
for(t[1] = 0; t[1] <= cnt[1]; t[1]++)
for(t[2] = 0; t[2] <= cnt[2]; t[2]++)
for(t[3] = 0; t[3] <= cnt[3]; t[3]++)
for(t[4] = 0; t[4] <= cnt[4]; t[4]++){
for(int k = 1; k <= 4; k++){
t[k]++;
int temp;
if(i > k)
temp = f[i-k][t[1]][t[2]][t[3]][t[4]] + a[i];
else temp = 0;
t[k]--;
f[i][t[1]][t[2]][t[3]][t[4]] = max(f[i][t[1]][t[2]][t[3]][t[4]], temp);
}
ans = max(ans, f[i][t[1]][t[2]][t[3]][t[4]]);
}
printf("%d\n", ans);
return 0;
}
```
嗯TLE，而且数组范围只能开20，只能过50分。
***
仔细观察后可以发现，我们的状态中除了4个卡片的维度是有必要的之外，$i$ 这一维是我们单纯为了省力写上去的，其实 $i$ 是可以被后面这四维算出来的吧？这其实就是个五元一次等式，有了4个未知数就可以推出另外一个，而 $i$ 是最大的，把它去了最赚。
这个五元一次方程是由我们的小乌龟走起来只能靠出牌，所以出了哪些牌就决定了他走了几步，设出了 $w_1, w_2, w_3,w_4$ 这么多的牌，那么小乌龟一共就走了 $ i=w_1 + 2*w_2+3*w_3+4*w_4$ 步，这样我们又把状态化简了好多，把这个 $i$ 代到上面的方程里就是新的方程了。
AC code:
```cpp
/*
* Author: xiaohei_AWM
* Date: 7.11
* Mutto: Face to the weakness, expect for the strength.
*/
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<ctime>
#include<utility>
#include<functional>
#include<cmath>
#include<vector>
#include<assert.h>
using namespace std;
#define reg register
#define endfile fclose(stdin);fclose(stdout);
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef std::pair<int,int> pii;
typedef std::pair<ll,ll> pll;
namespace IO{
char buf[1<<15],*S,*T;
inline char gc(){
if (S==T){
T=(S=buf)+fread(buf,1,1<<15,stdin);
if (S==T)return EOF;
}
return *S++;
}
inline int read(){
reg int x;reg bool f;reg char c;
for(f=0;(c=gc())<'0'||c>'9';f=c=='-');
for(x=c^'0';(c=gc())>='0'&&c<='9';x=(x<<3)+(x<<1)+(c^'0'));
return f?-x:x;
}
inline ll readll(){
reg ll x;reg bool f;reg char c;
for(f=0;(c=gc())<'0'||c>'9';f=c=='-');
for(x=c^'0';(c=gc())>='0'&&c<='9';x=(x<<3)+(x<<1)+(c^'0'));
return f?-x:x;
}
}
using namespace IO;
const int maxn = 351, maxm = 121;
int n, m, a[maxn], b[maxm], f[41][41][41][41];//f[w][x][y][z]表示到第i格，每种卡片分别还有 w x y z张的最大分值
//由于n可以被算出来
int cnt[5], ans;
int main(){
n = read(), m = read();
for(int i = 1; i <= n; i++) a[i] = read();
for(int i = 1; i <= m; i++) b[i] = read(), cnt[b[i]]++;
f[cnt[1]][cnt[2]][cnt[3]][cnt[4]] = a[1];
int t[5];
for(t[1] = cnt[1]; t[1] >= 0; t[1]--)
for(t[2] = cnt[2]; t[2] >= 0; t[2]--)
for(t[3] = cnt[3]; t[3] >= 0; t[3]--)
for(t[4] = cnt[4]; t[4] >= 0; t[4]--){
for(int k = 1; k <= 4; k++){
int pos = (cnt[1] - t[1]) + 2*(cnt[2] - t[2]) + 3*(cnt[3] - t[3]) + 4*(cnt[4] - t[4]) + 1;
t[k]++;
int temp;
if(pos > k)
temp = f[t[1]][t[2]][t[3]][t[4]] + a[pos];
else temp = 0;
t[k]--;
f[t[1]][t[2]][t[3]][t[4]] = max(f[t[1]][t[2]][t[3]][t[4]], temp);
}
ans = max(ans, f[t[1]][t[2]][t[3]][t[4]]);
}
printf("%d\n", ans);
return 0;
}
```