有没有dalao救我,70分

7AC 2WA 1RE

#include <algorithm>
#include <cstdio>
using namespace std;
int sum,totalw,n,ans[1001],dp[1000001],pre[1000001],w[1001];
int main() {
    scanf("%d%d",&totalw,&n);
    for (int i = 1;i <= n;i++) {
        scanf("%d",&w[i]);
        sum += w[i];
    }
    totalw = sum-totalw;
    dp[0] = 1;
    for (int i = 1;i <= n;i++)
        for (int j = totalw;j >= w[i];j--) {
            dp[j] += dp[j-w[i]];
            pre[j] = i;
        }
    dp[0] = 0;
    if (dp[totalw] == 0) printf("0");
    else if (dp[totalw] > 1) printf("-1");
    else {
        int now = totalw,cnt = 0;
        while (now) {
            ans[++cnt] = pre[now];
            now -= w[pre[now]];
        }
        sort(ans+1,ans+cnt+1);
        for (int i = 1;i <= cnt;i++) printf("%d%c",ans[i],i == cnt ? '\n' : ' ');
    }
    return 0;
}

1 条评论

  • @ 2018-02-02 13:35:21

    您A了吗
    代码中pre数组不能这样转移(在前一个状态为空的情况下)

    • @ 2018-02-02 18:10:22

      谢谢dalao,

      pre[j] = i;
      

      改成

      if (dp[j-w[i]]) pre[j] = i;
      

      就不RE了,可是还有两个点WA

    • @ 2018-02-02 20:21:16

      if(dp[j-w[i]]&&pre[j]==0) pre[j] = i;
      不能重复打印,比如状态a可以由一张牌转移到b,b可以由同一张牌转移到c,由c往前推到b,由b往前推倒a,你的代码打印出的牌是同一张

    • @ 2018-02-04 09:38:11

      谢谢,已经AC了

  • 1

信息

ID
1071
难度
7
分类
动态规划 | 背包 点击显示
标签
递交数
6284
已通过
1436
通过率
23%
被复制
13
上传者