关于dp数组的初始化方法导致WA在#11的问题
查看原帖
关于dp数组的初始化方法导致WA在#11的问题
443675
紊莫turtle楼主2022/5/2 10:44

RT,如下是我的最终AC代码:

#include <bits/stdc++.h>
#define min(a,b) a<b?a:b
#define max(a,b) a>b?a:b
#define int long long
using namespace std;
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
inline void write(int x){if (x < 0) x = ~x + 1, putchar('-');if (x > 9) write(x / 10);putchar(x % 10 + '0');}
int t[2011],c[2011],dp[4022],ans=2e12,maxx,n;
signed main()
{
	memset(dp,0x3f,sizeof(dp));dp[0]=0;
	n=read();
	for(int i=1;i<=n;i++) 	
	{
		t[i]=read()+1;c[i]=read();maxx=max(maxx,t[i]);
	}
	maxx+=n;
	for(int i=1;i<=n;i++)
		for(int j=maxx;j>=t[i];--j)
			dp[j]=min(dp[j],dp[j-t[i]]+c[i]);
	for(int i=n;i<=maxx;++i) ans=min(ans,dp[i]);
	write(ans);
}

注意到我用了memset来初始化数组。
但是我一开始写的是这样的(WA):

#include <bits/stdc++.h>
#define min(a,b) a<b?a:b
#define max(a,b) a>b?a:b
#define int long long
using namespace std;
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
inline void write(int x){if (x < 0) x = ~x + 1, putchar('-');if (x > 9) write(x / 10);putchar(x % 10 + '0');}
int t[2011],c[2011],dp[4022],ans=2e12,v,n;
signed main()
{
	for(int i=1;i<4002;++i) dp[i]=0x7f7f7f7f;dp[0]=0;
	n=read();
	for(int i=1;i<=n;i++) 
	{
		t[i]=read()+1;c[i]=read();v=max(v,t[i]);
	}
	v+=n;
	for(int i=1;i<=n;i++)
		for(int j=v;j>=t[i];--j)
			dp[j]=min(dp[j],dp[j-t[i]]+c[i]);
	for(int i=n;i<=v;++i) ans=min(ans,dp[i]);
	write(ans);
}

0x3f和0x7f我都试过,可能不是值的关系。
能否指点一二? thx

2022/5/2 10:44
加载中...