预计时间一个月,一天的量为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; }