dp循环顺序
分组背包
i,j,k表示同一个i，j下找到一个最优的k（或者说前i组j个代价下最优k），使得在代价j内最优
i,k,j 的话表示前i个k个j内取 f 的最值，和前“ i*k 个j内 ”取最值没有任何区别
背包约束一般放第三层
dp先考虑状态、方程
最后再考虑限制和边界
dp循环顺序一般是按照状态顺序来的
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int const mod=1e8;
int const N=1e2+7;
int const M=2e4+7;
int const S=1e2+7;
int n,s,m,fg,tol,d;
int v[N][S];
ll f[M];
int main(){
cin >> s >> n >> m;
for(int i=1;i<=s;++i){
for(int j=1;j<=n;++j){
cin >> v[j][i];
}
}
for(int i=1;i<=n;++i) sort(v[i]+1,v[i]+s+1);
for(int i=1;i<=n;++i){ //j循环在i循环之下，意为物品i为体积j时可以尝试放多次
for(int j=m;j>=1;--j){ //k循环在j循环之下，意为在体积为j时，找最优的k，在体积固定时i的派兵数唯一且为最大
for(int k=1;k<=s;++k){
if(j-(v[i][k]*2+1)>=0)
f[j]=max(f[j],f[j-(v[i][k]*2+1)]+i*k);
}
}
}
cout << f[m];
return 0;
}
投递新华三等公司7个岗位 >