当前位置: 代码迷 >> 综合 >> Vijos 1071 caioj 1411 动态规划2:打牌 (背包方案输出)
  详细解决方案

Vijos 1071 caioj 1411 动态规划2:打牌 (背包方案输出)

热度:119   发布时间:2023-09-20 19:35:48.0

非常奇怪的是,我在Vijos 1071能AC,在caioj 就只有50分

可以和前面一道题一样算方案,如果大于1就是多解

然后就输出方案就好了

#include<cstdio>
#include<cstring>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
using namespace std;const int MAXN = 112;
const int MAXM = 212345;
int w[MAXN], f[MAXM], n, tw;int main()
{scanf("%d%d", &tw, &n);REP(i, 0, n) scanf("%d", &w[i]);f[0] = 1;REP(i, 0, n)for(int j = tw; j >= w[i]; j--)f[j] += f[j-w[i]];	if(!f[tw]) puts("0");else if(f[tw] > 1) puts("-1");else{REP(i, 0, n){if(tw - w[i] >= 0 && f[tw - w[i]]) tw -= w[i];else printf("%d ", i + 1);}puts("");	}return 0;
}

 

  相关解决方案