80分求大佬调教QAQ
查看原帖
80分求大佬调教QAQ
1456854
renking666楼主2025/7/3 15:33

我的代码看起来没什么问题,但是为什么wa了4,6两个点QWQ

#include <bits/stdc++.h>
#include <set>
#include <vector> 
using namespace std;
int n,m,dp[32005];
vector<vector<struct node> > f(65);
struct node
{
	int v,p,q,idx;
}node[65];
bool cmp(struct node a,struct node b){
	return a.q<b.q;
}
int main() {
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		cin>>node[i].v>>node[i].p>>node[i].q;
    	node[i].idx=i;
	} 
	sort(node+1,node+1+m,cmp);
	for(int i=1;i<=m;i++)
		f[node[i].q].push_back(node[i]);
	for(int i=0;i<f[0].size();i++)  //遍历主件 
	{
		for(int j=n;j>=1;j--)
		{
			int a=f[0][i].v,b=f[0][i].p,c=f[0][i].q,idx=f[0][i].idx;
			if(a>j) continue;
			if(dp[j]>dp[j-a]+a*b) continue;  //不买直接continue 
			dp[j]=dp[j-a]+a*b;	//买
			if(f[idx].size()==0) continue;   //没有附件直接continue	
			else if(f[idx].size()==1){       //一个附件
				if(a+f[idx][0].v<=j){
					dp[j]=max(dp[j],dp[j-a-f[idx][0].v]+a*b+f[idx][0].v*f[idx][0].p);
				} 
			}else{   //两个附件 
			    int r1=0,r2=0,r3=0;
        	    if(a+f[idx][0].v<=j){
        	        r1= dp[j-a-f[idx][0].v]+a*b+f[idx][0].v*f[idx][0].p;//买第一个附件	
				} 
				if(a+f[idx][1].v<=j){
			    	r2= dp[j-a-f[idx][1].v]+a*b+f[idx][1].v*f[idx][1].p;//买第二个附件					
				} 
				//买两个附件 
				if(a+f[idx][0].v+f[idx][1].v<=j){
			    	r3= dp[j-a-f[idx][0].v-f[idx][1].v]+a*b+f[idx][0].v*f[idx][0].p+f[idx][1].v*f[idx][1].p;					
				}
			 	int res=max(r1,max(r2,r3));
				dp[j]=max(dp[j],res);
			}
		}
//			for(int k=1;k<=n;k++) cout<<dp[k]<<" ";
//			cout<<endl;	
	}		
	cout<<dp[n];
	return 0;
} 
2025/7/3 15:33
加载中...