建议加强数据
  • 板块P1776 宝物筛选
  • 楼主lndjy
  • 当前回复6
  • 已保存回复6
  • 发布时间2020/5/4 14:15
  • 上次更新2023/11/7 03:12:31
查看原帖
建议加强数据
196899
lndjy楼主2020/5/4 14:15

RT,这份错误的代码(不仅时间复杂度不对,而且是错误的)吸氧AC了,既没有TLE也没有WA

#include<iostream> 
using namespace std;
int f[1000005];
int v[1000005],w[1000005];
int cnt;
void add(int a,int b)
{
	cnt++;
	v[cnt]=a;
	w[cnt]=b;
}
int main()
{
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		int a,b,c;
		cin>>a>>b>>c;
		for(int j=1;j<=c;j++)//这里应该是j*=2,可是j++AC了
		{
			add(b*j,a*j);
			c-=j;
		}
		if(c) add(b*c,a*c);
	}
	for(int i=1;i<=cnt;i++)
	for(int j=m;j>=v[i];j--)
	f[j]=max(f[j],f[j-v[i]]+w[i]);
	cout<<f[m];
	return 0;
}
2020/5/4 14:15
加载中...