DP训练笔记

预计时间一个月,一天的量为1-2道左右,难度不均,黄-紫都有,后阶段紫

// https://www.luogu.com.cn/problem/P4141

// 对于任何一个物品对答案的贡献都是从1到n递推过去的,所以
// 只需要开一个相同的数组然后从头遍历一遍,把该物品对答案的贡献减去就可以了

#include<bits/stdc++.h>
using namespace std;
const int N=4020;
int dp[N],res[N],w[N],n,m;
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>w[i];
    dp[0]=1,res[0]=1;
    for(int i=1;i<=n;i++)
        for(int j=m;j>=w[i];j--) dp[j]=(dp[j]+dp[j-w[i]])%10;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(j<w[i]) res[j]=dp[j];
            //对于每个包含于i的物品答案数,用dp数-去未包含他的数即为答案数
            else res[j]=(dp[j]-res[j-w[i]]+10)%10;//别忘了相减取模要+模数
            cout<<res[j];
        }
        cout<<endl;
    }
    return 0;
}

//https://www.luogu.com.cn/problem/CF607B

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=2040,mod=1e9+7;
int n,t,dp[N][N],a[N];
signed main()
{
    std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=n;i>=1;i--){ //区间dp,这样的顺序是对的
        for(int j=i;j<=n;j++){
            //初始化:
            if(i==j) {dp[i][j]=1;continue;}
            if(i+1==j) {dp[i][j]=(a[i]==a[j]?1:2);continue;}
            dp[i][j]=1e18;
            //枚举区间长度
            for(int k=i;k<j;k++) 
                dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]);
            if(a[i]==a[j]) dp[i][j]=min(dp[i][j],dp[i+1][j-1]);
        }
    }
    cout<<dp[1][n];
    return 0;
}

//https://www.luogu.com.cn/problem/CF1513C

//可以肯定的是,对于任何一位的数来说,他能变得长度是确定得
//例如 9,它经过2两次变化长度一定是2,其它位对9这一位没影响
//所以先预处理来每个数能够变成得最多长度

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=3e5+10,mod=1e9+7;
string s;
int n,t,a[N],f[N],res,num,ans,m,k;
vector<vector<int>>dp(N+1,vector<int>(10));
void solve()
{
    cin>>s>>n; res=0;
    for(char c:s) res=(res+dp[n][c-'0'])%mod;
    cout<<res<<endl;
}
signed main()
{
    std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>t;
    //dp[i][j]为,数字j经过i次变换之后有多长
    //状态转移为 : 9先由1位变成2位,然后下一次变化后,8就是9,7就是8,以此类推
    for(int i=0;i<=9;i++) dp[0][i]=1;
    for(int i=1;i<=N;i++){
        for(int j=0;j<=8;j++) dp[i][j]=dp[i-1][j+1]%mod;
        dp[i][9]=(dp[i-1][1]+dp[i-1][0])%mod;
       // for(int j=0;j<=9;j++) cout<<dp[i][j]<<' ';cout<<endl;
    }
    while(t--){
        solve();
    }
    return 0;
}

// //另一种思路: 逢10进1,就有:
// if(i+j>=10) dp[i][j]=dp[i+j-10][0]+dp[i+j-10][1]%mod;
// else dp[i][j]=1;
// 如果i+j>10,那么操作后是两位,分别是1和0,而从j到10需要10-j步,还剩i+j-10步
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=3e5+10,mod=1e9+7;
string s;
int n,t,a[N],f[N],res,num,ans,m,k;
vector<vector<int>>dp(N+1,vector<int>(10));
void solve()
{
    cin>>s>>n; res=0;
    for(char c:s) res=(res+dp[n][c-'0'])%mod;
    cout<<res<<endl;
}
signed main()
{
    std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>t;
    //dp[i][j]为,数字j经过i次变换之后有多长
    //状态转移为 : 9先由1位变成2位,然后下一次变化后,8就是9,7就是8,以此类推
    for(int i=0;i<=9;i++) dp[0][i]=1;
    for(int i=1;i<=N;i++){
        for(int j=0;j<=9;j++)
            if(i+j>=10) dp[i][j]=dp[i+j-10][0]+dp[i+j-10][1]%mod;
            else dp[i][j]=1;
       // for(int j=0;j<=9;j++) cout<<dp[i][j]<<' ';cout<<endl;
    }
    while(t--){
        solve();
    }
    return 0;
}

//https://www.luogu.com.cn/problem/CF711C
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=205;
int dp[N][N][N],res=1e18,n,m,x;
/*
dp[i][j][k] 是第i个树,第j个颜色,当前是第k组
col[i]是当前的染色情况
c是 n x m 的花费
*/
int col[N],c[N][N];
signed main()
{
    std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n>>m>>x;
    for(int i=1;i<=n;i++) cin>>col[i];
    for(int i=1;i<=n;i++) 
        for(int j=1;j<=n;j++) cin>>c[i][j];
    //初始化
    memset(dp,0x3f,sizeof dp);
    //如果说第一位已经被染了,那么就不管了,因为要从第一位开始递推,如果没染那就都染一遍
    if(col[1]) dp[1][col[1]][1]=0;
    else for(int i=1;i<=m;i++) dp[1][i][1]=c[1][i];
    for(int i=2;i<=n;i++){
        if(col[i]){ //如果已经确定被染色
            for(int j=1;j<=m;j++){
                for(int k=1;k<=x;k++){
                    if(j!=col[i]) dp[i][col[i]][k]=min(dp[i][col[i]][k],dp[i-1][j][k-1]); //不同组
                    else dp[i][col[i]][k]=min(dp[i][col[i]][k],dp[i-1][col[i]][k]);// 同组
                }
            }
        }
        else{
            for(int j=1;j<=m;j++){
                for(int h=1;h<=m;h++){
                    for(int k=1;k<=x;k++){
                        if(j!=h) dp[i][j][k]=min(dp[i][j][k],dp[i-1][h][k-1]+c[i][j]);
                        else dp[i][j][k]=min(dp[i][j][k],dp[i-1][j][k]+c[i][j]);
                    }
                }
            }
        }
    }
    if(col[n]) res=dp[n][col[n]][x];
    else for(int i=1;i<=m;i++) res=min(res,dp[n][i][x]);
    cout<<(res>=1e18/2?-1:res);
    return 0;
}