试题 算法提高 学生节

记录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