大家帮忙看看为什么会re啊
查看原帖
大家帮忙看看为什么会re啊
168388
up_grant楼主2019/2/10 17:13

最里层那个while可能在答案的正确性上有点问题,但是为什么会re呢?数组也没越界啊

#include <iostream>
#include <cstring>
using namespace std;
int dp[5005][60],v,k,n,cost,worth,p1[60],ans,p2[60];
int main()
{
    cin>>k>>v>>n;
    memset(dp,-999999,sizeof(dp));
    dp[0][1]=0;
    for (int i=0;i<n;++i)
    {
        cin>>cost>>worth;
        for (int j=v;j>=cost;--j)
        {
            int a=1,b=1,m=1;
            for (int y=1;y<=k;++y)
            {
                p1[y]=dp[j][y];
                p2[y]=dp[j-cost][y]+worth;
            }
            while (m<=k&&(a<=k||b<=k))
            {
                if (p1[a]>p2[b])
                    dp[j][m]=p1[a++];
                else
                    dp[j][m]=p2[b++];
                if (m==0||dp[j][m]!=dp[j][m-1])
                    m++;
            }

        }
    }
    for (int y=1;y<=k;++y)
        ans+=dp[v][y];
    cout<<ans;
    return 0;
}

2019/2/10 17:13
加载中...