AC

AC

键盘敲碎夜深沉，代码如麻乱假真 · 发布于 2024-12-01 · 浏览 364 回复 1 
#include<bits/stdc++.h>
using namespace std;
int n,m;
int dp[2][500005];		//前i个鉴定后赚的更多的物品，凑的鉴定费为j的情况下的最大所得
struct magic{
	int p1,p2;		//鉴定前 鉴定后
};
vector<magic> d;
int main(){
	cin>>n>>m;		//物品数 卷轴价格
	string space;	//读下空格
	int bm=0;		//开始时的钱数，即普通的和鉴定之后更亏的普通卖价值总和
	int spz=0;		//全部魔法物品普通卖的价值总和
	int sp2h=0;		//其余的鉴定卖的收入总和
	getline(cin,space);
	for(int i=1;i<=n;i++){
		string s;
		getline(cin,s);
		if(s.find(' ')==-1){
			int p=stoi(s);
			bm+=p;		//直接卖
		}else{
			int p1=stoi(s.substr(0,s.find(' ')));
			int p2=stoi(s.substr(s.find(' ')+1));
			if(p2<=p1+m) bm+=p1;		//鉴定还亏，直接卖;
			else{
				d.push_back({p1,p2});
				spz+=p1;		//剩下物品普通卖
				sp2h+=p2-m;		//收入
			} 
		}
	}
	if(bm+spz<=m){		//一份鉴定费都不够
		cout<<bm+spz<<endl;		//全部普通卖
		return 0;
	}
	if(bm>=m){		//一开始就有钱鉴定
		cout<<bm+sp2h<<endl;		//全部都鉴
		return 0;
	}
	memset(dp,0xf0,sizeof dp);		//由于j必须要凑满（甚至大于） 所以初值先赋一个小的
	//因为鉴定费不能少只能多，那么只能初始化极小值，求的是刚好够
	for(int i=1;i<=d.size();i++){
		for(int j=0;j<=spz;j++){
			if(j-d[i].p1>=0)
				dp[i%2][j]=max(dp[(i-1)%2][j-d[i-1].p1]+d[i-1].p1,dp[(i-1)%2][j]+d[i-1].p2-m);
			  //dp[i][j]=max(dp[i-1][j-p1]+p1,dp[i-1][j]+p2-m);
			  //             又有了p1的鉴定费，相当于要凑的j少了p1
			  //                              鉴了，并且加上它获得的价值
			else 		//鉴定费太够了，防越界
				dp[i%2][j]=dp[(i-1)%2][j]+d[i-1].p2-m;
		}
	}
	int ans=0;
	for(int j=m-bm;j<=spz;j++)
		ans=max(ans,dp[d.size()%2][j]);
	cout<<ans+bm<<endl;
	return 0;
}

全部回复 共 1 条

  1. ------监狱栅栏------ #1 ·

    include

    include

    include

    include

    using namespace std; struct magic {

    int p1;
int p2;

    }; vector re; int dp[5001]; const int INF = 999999999; int main() {

    int money = 0; int t1 = 0,t2=0;
int n, m;
cin >> n >> m;
string s;
getline(cin, s);
for (int i = 0; i < n; i++) {
    getline(cin, s);
	if (s.find(' ') == -1) {
		money += stoi(s);
	}
	else {
		int p1 = stoi(s.substr(0, s.find(' ')));
		int p2 = stoi(s.substr(s.find(' ')+1));
		if (p2 - p1 <= m) money += p1;
		else {
			re.push_back({ p1,p2 });
			t2 += p2 - m;
			t1 += p1;
		}
	}
}
if (money >= m) {
	cout << money + t2;
	return 0;
}
if (money + t1 <= m) {
	cout << money + t1;
	return 0;
}
fill(dp, dp + t1 + 1, INF);
dp[0] = 0;
for (int i = 0; i < re.size(); i++)
{
	for (int j = t1; j>= re[i].p1; j--) {
		dp[j] = min(dp[j], dp[j - re[i].p1] + re[i].p2 - re[i].p1 - m);
	}
} 
int best = INF;
for (int i = m - money; i <= t1; i++) best = min(best, dp[i]);
cout << money + t2 - best;
return 0;

    }

发表回复