codeforces 2000~2100 DP

DP codeforces

我发现我状态设计水平好低

CF296B

sol

并没有想出一个好的直接做法（据说是容斥可做），考虑 $dp$

设 $f_{i,0/1,0/1}$ 表示前 $i$ 位存不存在数字使得 $s>w$ 和 $s<w$ 的方案数

转移是平凡的，枚举新数即可，答案是 $f_{n,1,1}$，本题不太在乎常数可以使用纯循环加位运算的写法，好实现

复杂度 $O(n)$，大概常数巨大有个 $100$ 的样子吧

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5;
const int mod=1e9+7;
int f[N][2][2];
int n;
char s[N],w[N];
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>s[i];
    for(int i=1;i<=n;i++) cin>>w[i];
    f[0][0][0]=1;
    for(int i=1;i<=n;i++){
        int a,b;
        for(int j=0;j<2;j++){
            for(int k=0;k<2;k++){//枚举来时的状态
                for(int nxt1=0;nxt1<=9;nxt1++){
                    if(s[i]=='?' or s[i]==(nxt1+'0')){
                        for(int nxt2=0;nxt2<=9;nxt2++){
                            if(w[i]=='?' or w[i]==(nxt2+'0')){
                                (f[i][j|(nxt1>nxt2)][k|(nxt1<nxt2)]+=f[i-1][j][k])%=mod;
                            }
                        }
                    }
                }
            }
        }
    }
    cout<<f[n][1][1]<<"\n";
}

总结

本题启发：当当前位状态和前后都完全无关的时候可以考虑直接用 $01$ 这种简单状态设计，没有一点后效性。同时在时间允许的情况下可以多循环一点来简约实现也是没有问题的，善于利用位运算。

评价：线性dp，难度大概中位绿，蓝有点虚高了

CF41D

sol

没太懂这玩意哪来的绿，可能看错题了？

难点应该在于输出方案吧，但是这种方案输出方式可以参考 atcoder dp contest 里面 lcs 这道题，思路是相似的

把问题转化成一个判断性问题先，设 $f_{i,j,k}$ 表示能不能在走到 $i$ 行 $j$ 列的时候获得 $k$ 个豌豆，这样设空间一点不紧张，这道题给的太宽松了，不太好评价

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=105;
bool f[N][N][N*10+5];
int n,m,k;
char s[N][N];
void out(int J,int W){
    cout<<J<<"\n";
    for(int i=n;i>1;i--){
        if(J>1)
        if(f[i-1][J-1][W-s[i][J]+'0']){
            cout<<"L";
            W-=(s[i][J]-'0');
            J--;
            continue;
        }
        if(J<m)
        if(f[i-1][J+1][W-s[i][J]+'0']){
            cout<<"R";
            W-=(s[i][J]-'0');
            J++;
            continue;
        }
    }
}
signed main(){
    ios::sync_with_stdio();
    cin.tie(0),cout.tie(0);
    cin>>n>>m>>k;
    k++;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>s[i][j];
        }
    }
    for(int i=1;i<=m;i++) f[1][i][s[1][i]-'0']=1;
    for(int i=2;i<=n;i++){
        for(int j=1;j<=m;j++){
            for(int w=(s[i][j]-'0');w<=1000;w++){
                if(j>1)f[i][j][w]|=f[i-1][j-1][w-s[i][j]+'0'];
                if(j<m)f[i][j][w]|=f[i-1][j+1][w-s[i][j]+'0'];
            }
        }
    }
    int ans=-1;
    for(int w=1000;w>=0;w--){
        if(w%k==0){
            for(int j=1;j<=m;j++){
                if(f[n][j][w]){
                    cout<<w<<"\n";
                    out(j,w);
                    return 0;
                }
            }   
        }
    }
    cout<<-1;
    return 0;
}

总结

本题启发：两维状态处理不了就多开一维就好了，输出方向反向转移即可

评价：除去输出就是水