【厌氧】 [USACO06DEC] The Fewest Coins G
  • 板块学术版
  • 楼主Rolen
  • 当前回复4
  • 已保存回复6
  • 发布时间2025/1/18 19:54
  • 上次更新2025/1/18 22:46:51
查看原帖
【厌氧】 [USACO06DEC] The Fewest Coins G
730113
Rolen楼主2025/1/18 19:54

第一次遇到厌氧,有没有能解释一下的?

#include<iostream>
#define max(x,y) (x<y?y:x)
#define min(x,y) (x<y?x:y)
using namespace std;
#define ll long long
const ll INF=1145141919810;
ll n,t,x[2000],y[2000],mx,sum,f[200004],g[200004],v[200000],w[200000],cnt;
int main(){
	scanf("%lld%lld",&n,&t);
	for(int i=1;i<=n;++i) scanf("%lld",&x[i]),mx=max(mx,x[i]);
	for(int i=1;i<=n;++i){
		scanf("%lld",&y[i]),sum+=y[i]*x[i];
		ll res=1;
		while(res<=y[i]){
			v[++cnt]=res*x[i],w[cnt]=res,y[i]-=res;
		}
		if(y[i]) v[++cnt]=y[i]*x[i],w[cnt]=y[i];
	}
	mx=min(mx+t,sum);
	for(int i=1;i<=mx;i++) g[i]=f[i]=1145141919810;
	g[0]=f[0]=0;
	for(int i=1;i<=cnt;++i)	for(int j=mx;j>=v[i];--j)	f[j]=min(f[j],f[j-v[i]]+w[i]);
	for(int i=1;i<=n;++i) for(int j=x[i];j<=mx-t;++j) g[j]=min(g[j-x[i]]+1,g[j]);
	ll ans=INF;
	for(int i=t;i<=mx;++i) ans=min(ans,f[i]+g[i-t]);
	if(ans>=INF) return cout<<-1,0;
	cout<<ans;
}
2025/1/18 19:54
加载中...