试题 算法提高 学生节
记录01背包的问题
这里的t[i] 作为最晚可以观看节目的下标
k作为背包的最大称重量 即可以看的节目数
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
typedef long long ll;
const int N =1e6+10;
int n,m,T;
struct cmp {
bool operator()(const int&a,const int&b) const {
return a>b;
}
};
int v[1010];
int t[1010];
int dp[1010][1010];
int main() {
cin >> n>>m>>T;
for(int i =1;i<=n;i++){
cin >>v[i];
}
memset(dp,0,sizeof(dp));
for(int i=1;i<=T;i++){
cin >> t[i];
}
for(int i=1;i<=T;i++){
for(int j = 1;j <=t[i];j++){
for(int k = 1;k<=m;k++){
dp[j][k]=max(dp[j-1][k],dp[j-1][k-1]+v[j]);
}
}
cout<<dp[t[i]][m]<<endl;
}
return 0;
}
//3
//-1 -2 -3
