试题 A: 2022
题意:2022分为不同十个不同的正整数的方案数。
思路:状态机动态规划
答案:379187662194355221
const int N=2e3+100;
ll f[N][N][11][2]; // 前i个数 选k个不同的数 和为j 0:不选i 1:选i
void solve() {
int n,m;
cin>>n>>m;
f[0][0][0][0]=1;
for(int i=1;i<=n;i++) {
for(int j=0;j<=n;j++) {
for(int k=0;k<=m;k++) {
f[i][j][k][0]+=f[i-1][j][k][0]+f[i-1][j][k][1];
if(j>=i&&k>=1)
f[i][j][k][1]+=f[i-1][j-i][k-1][0]+f[i-1][j-i][k-1][1];
}
}
}
cout<<f[n][n][m][0]<<endl;
}
试题 F: 费用报销
int f[410][5010]; // 前i天,不超j面值的最大面值
int w[410];
int mon[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
void solve() {
int n,m,k;
cin>>n>>m>>k;
for(int i=1;i<=12;i++) mon[i]+=mon[i-1];
for(int i=1;i<=n;i++) {
int m,d,v;
cin>>m>>d>>v;
int t=mon[m-1]+d;
w[t]=max(w[t],v);
}
for(int i=1;i<=366;i++) {
for(int j=0;j<=m;j++) {
f[i][j]=f[i-1][j];
if(j>=w[i]&&i>=k)
f[i][j]=max(f[i][j],f[i-k][j-w[i]]+w[i]);
else if(j>=w[i])
f[i][j]=max(f[i][j],w[i]);
}
}
cout<<f[366][m]<<endl;
}
还有第二题? 感觉就是个线段问题的背包.
就是做一下去年的dp题,要比赛了。
哦,大佬加油!
大佬 这个都是啥题啊???
去年蓝桥杯B组决赛的dp题
谢谢大佬 大佬加油
应该也可以从小到大依次选择不同的数。 选择前i个数 最后一个数是j 且和为k dp[i][j][k] , dp[11][2023][2023];