第三组数据为什么过不了？

新年趣事之打牌
帝皇法老 LV 7 @ 2013-08-18 21:34:18

#include <iostream>
#include <cstring>
using namespace std;

long long W[108],F[100008],P[108][100008];
bool xuan[108];

int main()
{
int TW,N;
cin >> TW >> N;
for(int i=1;i<=N;++i)
cin >> W[i];

F[0]=1;
for(int i=1;i<=N;++i)
for(int j=TW;j>=W[i];--j)
{
F[j]+=F[j-W[i]];
if(F[j]==8)
F[j]=3;
}
if(F[TW]==0)
{
cout << 0 << endl;
return 0;
}
else if(F[TW]>1)
{
cout << -1 << endl;
return 0;
}

memset(F,false,sizeof(F));

F[0]=true;
memset(P,-1,sizeof(P));
for(int i=1;i<=N;++i)
for(int j=TW;j>=0;--j)
{
if(j>=W[i] && F[j-W[i]])
{
P[i][j]=i;
F[j]=F[j-W[i]];
}
else P[i][j]=P[i-1][j];
}

int n=P[N][TW],tw=TW;
while(n>=0 && tw>=0)
{
xuan[n]=true;
tw-=W[n];
n=P[n][tw];
}

for(int i=1;i<=N;++i)
if(!xuan[i])
cout << i << ' ';
return 0;
}

尘世美 LV 8 @ 2015-04-22 17:38:54

我的代码也是过不了#3数据
尘世美 LV 8 @ 2015-04-22 17:33:40

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define sz 110
#define for1(v,a,b) for (int v=a;v<=b;v++)
using namespace std;
int w[sz],lw,pre[sz*sz*sz],f[sz*sz*sz];
bool p[sz];
int n,sum;
int main(){
freopen("p1.in","r",stdin);
scanf("%d%d",&lw,&n);
sum=0;
for1(i,1,n){
scanf("%d",&w[i]);
sum+=w[i];
}

f[0]=1;
for1(i,1,n)
for(int j=sum;j>=w[i];j--)
if (f[j-w[i]]){
f[j]+=f[j-w[i]];
pre[j]=i;
}
if (f[lw]==0) printf("0");
else
if (f[lw]>1) printf("-1");
else{
int t=lw;
while (pre[t]!=0){
p[pre[t]]=true;
t-=w[pre[t]];
}
for1(i,1,n)
if (!p[i]) printf("%d ",i);
}
return 0;
}
帝皇法老 LV 7 @ 2013-08-19 15:48:19

好吧，我知道了，把最优解覆盖了
帝皇法老 LV 7 @ 2013-08-19 00:03:16

是#3组数据，也就是第四个数据，我看错了
- Mycraft LV 7 @ 2014-06-20 23:33:13
  
  我也没过到这个点，不过什么是最优解，不是说多解输-1么。。0.0