100pts但没AC,玄关
查看原帖
100pts但没AC,玄关
1151923
lzsy0313楼主2025/1/20 11:39

Subtack #2 两个点过不了

#include <iostream>
#define MAXN 32005
using namespace std;
int n,m,v1,p1,q1;
int f[MAXN]; 
int s[MAXN];
struct node{
	int v,w; //v价值 w重量 b附件  
	bool sf;
}a[MAXN][3];
int tot,sum;

int main(){
//	freopen("dsf.in","r",stdin);
//	freopen("dsf.out","w",stdout);
	cin >>n >>m;
	for(int i=1;i<=m;i++){
		cin >>v1 >>p1 >>q1;
		tot++;
		if(q1==0) a[tot][0].v=v1*p1,a[tot][0].w=v1;
		else{
			a[q1][s[q1]+1].v=a[q1][s[q1]].v+v1*p1;
			a[q1][s[q1]+1].w=a[q1][s[q1]].w+v1;
			s[q1]++;
			sum++;
		}
	}
//	for(int i=1;i<=tot;i++){
//		for(int j=0;j<=2;j++){
//			cout <<a[i][j].v <<" "<<a[i][j].w <<" ";
//		}
//		cout <<endl;
//	}
	
	for(int i=1;i<=tot;i++){
		for(int j=n;j>=0;j--){
			if(j>=a[i][0].w) f[j]=max(f[j],f[j-a[i][0].w]+a[i][0].v);
			if(j>=a[i][1].w) f[j]=max(f[j],f[j-a[i][1].w]+a[i][1].v);
			if(j>=a[i][2].w) f[j]=max(f[j],f[j-a[i][2].w]+a[i][2].v);
		}
	} 
	cout <<f[n] <<endl;
//	for(int i=1;i<=m;i++){
//		for(int j=100;j<=n;j+=100){
//			cout <<f[i][j] <<" ";
//		}
//		cout <<endl;
//	} 
//	cout <<f[m][n];
//	fclose(stdin);
//	fclose(stdout);
	return 0;
}
/*
  i   1    2     3     4     5  
j100  0    0     0     0     0
 200  0    0     0     0     0 
 300  0    0     0     0     0
 400  0    0     0     1200  1200
 500  0    0     0     1200  1200
 600  0    0     0     1200  1200
 700  0    0     0     1200  1200
 800  1600 1600  1600  1600  1600
 900  1600 1600  1600  1600  2200
 1000 1600 1600  1600  1600  2200
 1100 1600 1600  3100  
 1200 1600 3600  3600
 1300 1600 3600  3600
 1400 1600 3600  3600
 1500 1600 3600  5100
*/
2025/1/20 11:39
加载中...