紊莫 @ 2022-05-02 10:44:17
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
by Hisaishi_Kanade @ 2022-05-02 11:08:14
@Velvet 你的数组是long long
,0x7f7f7f7f
赋的值太小了。
by 紊莫 @ 2022-05-02 11:11:39
@bye_wjx 原来按位的memset的0x3f是>0x7f7f7f7f的,thx
by 紊莫 @ 2022-05-02 11:14:03
又AC了。此贴结。