DP的训练
codesonic
2018-07-17 20:25:38
因为我DP太弱了所以要多加训练啊。。。现在放一个专版DP题来切，做一道就放一道，按从简单到难由上到下（个人看法）
### 1.[P1052 过河](https://www.luogu.org/problemnew/show/P1052)
如果不用离散就是一道简单DP
因为独木桥长度太长了，而石头少，所以我们可以把它离散下来
然后就是简单题了
```cpp
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=400010;
int l,s,t,m,ans;
int f[maxn];
int a[maxn],d[maxn],rck[maxn];
bool check[maxn];
#define ll int
namespace fib{char b[300000]= {},*f=b;}
#define gc ((*fib::f)?(*(fib ::f++)):(fgets(fib::b,sizeof(fib::b),stdin)?(fib::f=fib::b,*(fib::f++)):-1))
inline void in(ll &x){x=0;char c;bool f=0;while((c=gc)>'9'||c<'0')if(c=='-')f=!f;x=c-48;while((c=gc)<='9'&&c>='0')x=x*10+c-48;if(f)x=-x;}
namespace fob{char b[300000]= {},*f=b,*g=b+300000-2;}
#define pob (fwrite(fob::b,sizeof(char),fob::f-fob::b,stdout),fob::f=fob::b,0)
#define pc(x) (*(fob::f++)=(x),(fob::f==fob::g)?pob:0)
struct foce{~foce(){pob;fflush(stdout);}} _foce;
namespace ib{char b[100];}
inline void out(ll x){if(x==0){pc(48);return;}if(x<0){pc('-');x=-x;}char *s=ib::b;while(x) *(++s)=x%10,x/=10;while(s!=ib::b) pc((*(s--))+48);}
inline void outn(ll x){out(x);pc('\n');}
inline void swap(ll &x,ll &y){ll t=x;x=y;y=t;}
inline ll jdz(ll x){return x>0?x:-x;}
inline ll max(ll x,ll y){return x>y?x:y;}
inline ll min(ll x,ll y){return x<y?x:y;}
int main()
{
in(l);in(s);in(t);in(m);
for(register int i=1;i<=m;++i)
in(a[i]);
sort(a+1,a+m+1);
for(register int i=1;i<=m;i++){
d[i]=(a[i]-a[i-1])%2520;
}
memset(check,0,sizeof(check));
for(register int i=1;i<=m;i++){
check[a[i]=a[i-1]+d[i]]=1;
}
int len=a[m];
for(register int i=1;i<=len+t;++i){
f[i]=m;
}
f[0]=0;
for(register int i=1;i<=len+t;++i){
for(int j=s;j<=t;j++){
if(i-j>=0)
f[i]=min(f[i],f[i-j]);
f[i]+=check[i];
}
}
ans=m;
for(register int i=len;i<len+t;i++)
ans=min(ans,f[i]);
outn(ans);
return 0;
}
```
### 2.[车的放置](https://www.luogu.org/problemnew/show/P1350)
一道神仙题，题解里给出了吊打各种做法的做法。。。
其他做法窝根本想不到啊。。。
f[i][j]表示前i行放j个的方案，然后记录每一列的高度，翻转一下dp就行了
可以学习的地方:
### 对于不规则图形，可以通过反转使它规则
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=2e3+5;
const int maxn=2010,modd=100003;
int f[maxn][maxn],h[maxn];
inline void read(int &x) {
x=0;
int f=1;
char c=getchar();
while(c<'0'||c>'9') {
if(c=='-')f=-f;
c=getchar();
}
while(c>='0'&&c<='9') {
x=x*10+c-'0';
c=getchar();
}
x*=f;
}
int a,b,c,d,k;
int main()
{
read(a);read(b);read(c);read(d),read(k);
for(int i=1;i<=c;i++)
f[i][0]=1,h[i]=d;
for(int i=1;i<=a;i++)
h[c+i]=d+b,f[c+i][0]=1;
for(int i=c+1;i<=a+c;i++)
f[i][0]=1,h[i]=b+d;
f[0][0]=1;
for(int i=1;i<=a+c;i++)
for(int j=1;j<=k;j++)
f[i][j]=(f[i-1][j]+f[i-1][j-1]*(h[i]-j+1))%modd;
printf("%d",f[a+c][k]);
return 0;
}
```
### 3.[乌龟棋](https://www.luogu.org/problemnew/show/P1541)
一道不错的递推题
四维DP
每一维枚举一种卡牌的数量
枚举“我从哪里来（即使用了哪一张卡牌到此地）”进行得分计算
发现有点像DAG上的最短路=_=
就这么做了
```cpp
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int f[55][55][55][55];
int a[355];
int x[5];
int main()
{
memset(x,0,sizeof(x));
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1;i<=m;i++){
int tmp;
scanf("%d",&tmp);
x[tmp]++;
}
f[0][0][0][0]=a[1];
for(int i=0;i<=x[1];i++)
for(int j=0;j<=x[2];j++)
for(int k=0;k<=x[3];k++)
for(int l=0;l<=x[4];l++){
int v=1+i+2*j+3*k+4*l;
if(i!=0)
f[i][j][k][l]=max(f[i][j][k][l],f[i-1][j][k][l]+a[v]);
if(j!=0)
f[i][j][k][l]=max(f[i][j][k][l],f[i][j-1][k][l]+a[v]);
if(k!=0)
f[i][j][k][l]=max(f[i][j][k][l],f[i][j][k-1][l]+a[v]);
if(l!=0)
f[i][j][k][l]=max(f[i][j][k][l],f[i][j][k][l-1]+a[v]);
}
printf("%d\n",f[x[1]][x[2]][x[3]][x[4]]);
return 0;
}
```
### 4.[取数]
因为不能拿出来公开所以没有链接
设f[i][j][1]为i到j区间，B先取剩的答案，f[i][j][0]为i到j区间，A先取剩的答案。
显然当我们取到f[l][r][0]时，答案=min(f[l+1][r][1],f[l][r-1][1])
于是
```cpp
#include<cstdio>
#include<iostream>
using namespace std;
int a[2010];
int f[2010][2010][2];//0=A,1=B;
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
f[i][i][0]=f[i][i][1]=a[i];
}
for(int len=2;len<=n;len++){
for(int i=1,j=len;j<=n;i++,j++){
f[i][j][0]=min(f[i+1][j][1],f[i][j-1][1]);
f[i][j][1]=max(f[i+1][j][0],f[i][j-1][0]);
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
printf("%d ",f[i][j][0]);
}
printf("\n");
}
printf("\n\n");
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
printf("%d ",f[i][j][1]);
}
printf("\n");
}
return 0;
}
```
### 5.[染色](https://www.luogu.org/problemnew/show/P4170)
首先设f[i][j]为从i到j最少染色次数，显然对于任何的i，f[i][i]=1；
接下来对于其他的情况，若c[i]=c[j]，显然f[i][j]可以由然f[i][j-1]或然f[i+1][j]一次染掉。
所以
f[i][j]=min(f[i+1][j],f[i][j-1])
对于c[i]!=c[j],我们需要枚举个断点，分成两次染掉
所以对于i到j-1中所有的k
f[i][j]=min(f[i][j],f[i][k]+f[k+1][j])
```cpp
#include<cstdio>
#include<cstring>
using namespace std;
inline int min(int a,int b){
return a<b?a:b;
}
char c[60];
int f[60][60];
int main()
{
scanf("%s",c);
memset(f,0x7F,sizeof(f));
int n=strlen(c);
for(int i=0;i<n;i++){
f[i][i]=1;
}
for(int len=1;len<=n;len++)
for(int i=0,j=len;j<=n;i++,j++)
if(c[i]==c[j])
f[i][j]=min(f[i+1][j],f[i][j-1]);
else
for(int k=i;k<j;k++)
f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]);
printf("%d",f[0][n-1]);
return 0;
}
```
### 6.[单人纸牌](https://www.luogu.org/problemnew/show/P1837)
对于每一个状态计数，记录成为下一个状态的概率，比如到了某一状态有x种选择方法，则对这几种选择方案造成的状态的概率加上1/x即可
```cpp
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
long double f[5][5][5][5][5][5][5][5][5];
bool check[10][10];
char c[10][10];
char tmp[20];
int head[20];
int main() {
for(int i=1; i<=9; i++) {
gets(tmp);
c[i][1]=tmp[9];
c[i][2]=tmp[6];
c[i][3]=tmp[3];
c[i][4]=tmp[0];
}
f[0][0][0][0][0][0][0][0][0]=1;
for(head[1]=0; head[1]<=4; head[1]++)
for(head[2]=0; head[2]<=4; head[2]++)
for(head[3]=0; head[3]<=4; head[3]++)
for(head[4]=0; head[4]<=4; head[4]++)
for(head[5]=0; head[5]<=4; head[5]++)
for(head[6]=0; head[6]<=4; head[6]++)
for(head[7]=0; head[7]<=4; head[7]++)
for(head[8]=0; head[8]<=4; head[8]++)
for(head[9]=0; head[9]<=4; head[9]++) {
if(long double p=f[head[1]][head[2]][head[3]][head[4]][head[5]][head[6]][head[7]][head[8]][head[9]]) {
int cnt=0;
memset(check,0,sizeof(check));
for(int i=1; i<9; i++) {
for(int j=i+1; j<=9; j++) {
if(head[i]+1<=4 && head[j]+1<=4 && c[i][head[i]+1]==c[j][head[j]+1]) {
check[i][j]=1;
cnt++;
}
}
}
if(cnt) {
for(int i=1; i<9; i++) {
for(int j=i+1; j<=9; j++) {
if(check[i][j]) {
head[i]++,head[j]++;
f[head[1]][head[2]][head[3]][head[4]][head[5]][head[6]][head[7]][head[8]][head[9]]+=p/(long double)(cnt*1.0);
head[i]--,head[j]--;
}
}
}
}
}
}
printf("%.6Lf",f[4][4][4][4][4][4][4][4][4]);
}
```
### 7. [[ZJOI2005]午餐](https://www.luogu.org/problemnew/show/P2577)
毒瘤ZJOI题~~不是可怜题没兴趣~~
显然吃饭慢的要先打饭
排序，前缀和优化
设f i,j 表示1窗口用了i时间，第j个人最早吃完饭的时间
然后就和01背包那样做做
```cpp
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
using namespace std;
const int maxn=210;
struct node{
int x,y;
}a[maxn];
int b[maxn],n;
int f[maxn][maxn*maxn];
inline int min(int a,int b){
return a>b?b:a;
}
inline int max(int a,int b){
return a<b?b:a;
}
inline bool cmp(node a,node b){
return a.y>b.y;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d%d",&a[i].x,&a[i].y);
sort(a+1,a+1+n,cmp);
memset(f,127,sizeof f);
f[0][0]=0;
for(int i=1;i<=n;i++)
b[i]=b[i-1]+a[i].x;
for(int i=1;i<=n;i++){
for(int j=0;j<=b[i];j++){
f[i][j]=min(f[i][j],max(f[i-1][j],b[i]+a[i].y-j));
if(j>=a[i].x)
f[i][j]=min(f[i][j],max(f[i-1][j-a[i].x],a[i].y+j));
}
}
int ans=(1<<30);
for(int i=1;i<=b[n];i++)
ans=min(ans,f[n][i]);
return printf("%d\n",ans),0;
}
```
### 8. [P1270 “访问”美术馆](https://www.luogu.org/problemnew/show/P1270)
树形DP，有个很有用的技巧就是可以边dfs边输入，学习到了
主要就是类似背包的方法分配给左子树和右子树时间
```cpp
// luogu-judger-enable-o2
#include<iostream>
#include<cstdio>
using namespace std;
int n;
int cnt=0;
#define in2(x,y) in(x);in(y)
#define ll int
namespace fib{char b[300000]= {},*f=b;}
#define gc ((*fib::f)?(*(fib ::f++)):(fgets(fib::b,sizeof(fib::b),stdin)?(fib::f=fib::b,*(fib::f++)):-1))
inline void in(ll &x){x=0;char c;bool f=0;while((c=gc)>'9'||c<'0')if(c=='-')f=!f;x=c-48;while((c=gc)<='9'&&c>='0')x=x*10+c-48;if(f)x=-x;}
namespace fob{char b[300000]= {},*f=b,*g=b+300000-2;}
#define pob (fwrite(fob::b,sizeof(char),fob::f-fob::b,stdout),fob::f=fob::b,0)
#define pc(x) (*(fob::f++)=(x),(fob::f==fob::g)?pob:0)
struct foce{~foce(){pob;fflush(stdout);}} _foce;
namespace ib{char b[100];}
inline void out(ll x){if(x==0){pc(48);return;}if(x<0){pc('-');x=-x;}char *s=ib::b;while(x) *(++s)=x%10,x/=10;while(s!=ib::b) pc((*(s--))+48);}
inline void outn(ll x){out(x);pc('\n');}
inline void swap(ll &x,ll &y){ll t=x;x=y;y=t;}
inline ll jdz(ll x){return x>0?x:-x;}
inline ll max(ll x,ll y){return x>y?x:y;}
inline ll min(ll x,ll y){return x<y?x:y;}
const int maxn=1010;
int f[maxn][maxn];
void solve(){
int idx,tim,l,r;
in2(tim,idx);
tim<<=1;
int root=++cnt;
if(idx)
for(int i=1;i<=n;++i)
f[root][i]=min((i-tim)/5,idx);
else{
l=cnt+1;
solve();
r=cnt+1;
solve();
for(int i=tim;i<=n;i++)
for(int j=0;j<=i-tim;j++)
f[root][i]=max(f[root][i],f[l][j]+f[r][i-j-tim]);
}
}
int main(){
in(n);
n--;
solve();
outn(f[1][n]);
return 0;
}
```
### 9.[[AHOI2009]中国象棋](https://www.luogu.org/problemnew/show/P2051)
毒瘤题，我抄题解没开llWA了无数遍过的
dp[i][j][k]表示放了前i行，有j列是有1个棋子，有k列有两个棋子
我们可以不用状压记录j和k分别是哪些（因为不影响后面），于是我们可以这样设。。。
然后一遍推过去就行啦=w=
不过这种题给我想我呀是真的想不到qwq。。。不像单人纸牌我能想。。。
还是要多加训练啊
```cpp
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int modd=9999973;
int f[110][110][110];
inline int C(int num){
return num*(num-1)/2;
}
int main(){
int n,m;
scanf("%d%d",&n,&m);
f[0][0][0]=1;
for(int i=0;i<n;i++){
for(int j=0;j<=m;j++){
for(int k=0;j+k<=m;k++){
if(f[i][j][k]){
f[i+1][j][k]=(f[i+1][j][k]+f[i][j][k])%modd;
if(m-j-k>=1)
f[i+1][j+1][k]=(f[i+1][j+1][k]+f[i][j][k]*(m-j-k))%modd;
if(j>=1)
f[i+1][j-1][k+1]=(f[i+1][j-1][k+1]+f[i][j][k]*j)%modd;
if(m-j-k>=2)
f[i+1][j+2][k]=(f[i+1][j+2][k]+f[i][j][k]*C(m-j-k))%modd;
if(m-j-k>=1&&j>=1)
f[i+1][j][k+1]=(f[i+1][j][k+1]+f[i][j][k]*(m-j-k)*j)%modd;
if(j>=2)
f[i+1][j-2][k+2]=(f[i+1][j-2][k+2]+f[i][j][k]*C(j))%modd;
}
}
}
}
long long ans=0;
for(int i=0;i<=m;i++)
for(int j=0;i+j<=m;j++)
ans=(ans+f[n][i][j])%modd;
printf("%lld\n",ans);
return 0;
}
```
### 10.[[Code+#1]找爸爸](https://www.luogu.org/problemnew/show/P4059)
神仙题，状态的设计十分巧妙。实在不是考场上随随便便能想出来的Orz
（udpdate 一年后，现在觉得很好想了）
设f[i][j][k]为第一个字符串匹配了i，第二个匹配了j个，k=0，表示此时两个子字符串末尾都没有空格，k=1，第一个有空格，k=2，第二个有空格，因为如果两个都是空格答案肯定不是最优，所以不需要考虑
然后直接做就行了
```cpp
// luogu-judger-enable-o2
#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
using namespace std;
const int maxn=3010;
const int INF=(1<<30);
char s1[maxn],s2[maxn];
int n,m,x[maxn],y[maxn],fa[260];
int dis[maxn][maxn],a,b;
int f[maxn][maxn][3];
inline int maxx(int a,int b){
return a<b?b:a;
}
inline int maxx3(int a,int b,int c){
return maxx(a,maxx(b,c));
}
int main()
{
fa['A']=0,fa['T']=1,fa['G']=2,fa['C']=3;
scanf("%s\n%s",s1+1,s2+1);
n=strlen(s1+1),m=strlen(s2+1);
for(int i=1;i<=n;i++){
x[i]=fa[s1[i]];
}
for(int i=1;i<=m;i++){
y[i]=fa[s2[i]];
}
for(int i=0;i<=3;i++)
for(int j=0;j<=3;j++)
scanf("%d",&dis[i][j]);
scanf("%d%d",&a,&b);
for(int i=1;i<=maxx(n,m);i++){
f[i][0][0]=f[0][i][0]=f[i][0][2]=f[0][i][1]=-INF;
f[i][0][1]=f[0][i][2]=-a-b*(i-1);
}
f[0][0][1]=f[0][0][2]=-INF;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
f[i][j][0]=maxx3(f[i-1][j-1][0],f[i-1][j-1][1],f[i-1][j-1][2])+dis[x[i]][y[j]];
f[i][j][1]=maxx3(f[i][j-1][1]-b,f[i][j-1][2]-a,f[i][j-1][0]-a);
f[i][j][2]=maxx3(f[i-1][j][2]-b,f[i-1][j][1]-a,f[i-1][j][0]-a);
}
}
printf("%d\n",maxx3(f[n][m][0],f[n][m][1],f[n][m][2]));
return 0;
}
```
### 11.[卫宫家今天的饭](https://www.luogu.com.cn/problem/P5664)
## 减去无用状态！！！
优化DP时，可以考虑什么状态设计最有用，当前剩余什么无用状态，然后无用状态怎么丢掉（两个状态改为一个状态）
很好的启示，我当时CSP时大脑空白，练度不够。
然后要个容斥，把合法方案改为总方案-不合法方案
这个容斥也要记下来。
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=114,maxm=2010;
const int mod=998244353;
int n,m,a[maxn][maxm],s[maxn];
int f[maxn][maxn<<1],g[maxn][maxn];
//f:不合法，g：总方案
//fijk表示第i行 col列的个数选了j，其他列选了k
//不关心jk具体数值，仅需要jk的差
// 故优化为j=j-k
//fij表示第i行col列的个数比其他列多了j个
signed main(){
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
scanf("%lld",&a[i][j]);
(s[i]+=a[i][j])%=mod;
}
int ans=0;
for(int col=1;col<=m;col++){
memset(f,0,sizeof f);
f[0][n]=1;
for(int i=1;i<=n;i++)
for(int j=n-i;j<=n+i;j++)
f[i][j]=(f[i-1][j] + (f[i-1][j-1]*a[i][col]*1ll)%mod + (1ll*f[i-1][j+1]*((s[i]-a[i][col])%mod))%mod)%mod;
for(int i=1;i<=n;i++)
ans=(ans+f[n][n+i])%mod;
}
g[0][0]=1;
for(int i=1;i<=n;i++)
for(int j=0;j<=n;j++)
g[i][j]=(g[i-1][j]+(j>0?g[i-1][j-1]*s[i]*1ll%mod:0))%mod;
for(int i=1;i<=n;i++) ans=(ans-g[n][i]+mod)%mod;
printf("%lld\n",(mod-ans)%mod);
}
```
注意一下下标为负数的ub和取模技艺即可
### 12.[地精部落](https://www.luogu.org/problemnew/show/P2467)
对于一个状态f[i][j]，可以从i-1得出，对于j与j-1不相邻，因为不相邻所以没有什么影响（意会，大概就是不相邻的话不会有影响）。。。所以f[i][j]=f[i][j-1]，如果相邻，那么除去第一个，后面的状态变成f[i-1][j-1]（仍利用第一种情况的性质，山峰和山谷交换后的方案数相同，此时j-1变为山谷，因为相同可以假装他是山峰，少了一个数所以i-1），发现此时区间的含义变了，应改为i-1+1-(j-1)=i-j-1。大概就是f[j+1][i]和f[j][i-1]概念差不多。。。
最后把两种加起来就可以了
~~DP真的是解释不清楚qwq~~
```cpp
#include<iostream>
#include<cstdio>
using namespace std;
int f[4010][2];//滚动数组优化
int main() {
int n,k;
f[2][0]=1;
scanf("%d%d",&n,&k);
for(int i=3;i<=n;i++)
for(int j=2;j<=i;j++)
f[j][i&1]=(f[j-1][i&1]+f[i-j+1][(i-1)&1])%k;
int ans=0;
for(int i=2;i<=n;i++){
ans=(ans+f[i][n&1])%k;
}
printf("%d",(ans<<1)%k);
return 0;
}
```