关于dp数组的初始化方法导致WA在#11的问题

CF19B Checkout Assistant

紊莫 @ 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 long0x7f7f7f7f赋的值太小了。


by 紊莫 @ 2022-05-02 11:11:39

@bye_wjx 原来按位的memset的0x3f是>0x7f7f7f7f的,thx


by 紊莫 @ 2022-05-02 11:14:03

又AC了。此贴结。


|