此题目:智灵班普及-背包补充 - 信友队
我抱着先看看这样样例过不了能拿几分的想法提交了上去,结果AC了?
#include<bits/stdc++.h>
#define I using
#define AK namespace
#define IOI std
#define i_ak return
#define ioi 0
I AK IOI;
int n,a[1005],dp[100005],sum,t,l[1005],r[1005],b,c;
int main(){
//freopen("","r",stdin);
//freopen("","w",stdout);
memset(dp,-1,sizeof dp);
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
sum+=a[i];
}
dp[50000]=0;
for(int i=1;i<=n;i++){
for(int j=-sum;j<=sum;j++){
if(dp[j+50000]!=-1){
if(j-a[i]>=-sum)dp[j-a[i]+50000]=max(dp[j-a[i]+50000],dp[j-a[i]+50000]+a[i]);
if(j+a[i]<=sum)dp[j+a[i]+50000]=max(dp[j+a[i]+50000],dp[j+a[i]+50000]+a[i]);
}
}
}
t=dp[50000];
cout<<t<<endl;
int j=0;
for(int i=n;i>=1;i--){
if(j-a[i]>=-sum&&dp[j+50000]==dp[j-a[i]+50000]+a[i])r[++c]=a[i],j-=a[i];
else if(j+a[i]<=sum&&dp[j+50000]==dp[j+a[i]+50000]+a[i])l[++b]=a[i],j+=a[i];
}
cout<<b<<' '<<c<<endl;
for(int i=1;i<=b;i++)cout<<l[i]<<' ';
cout<<endl;
for(int i=1;i<=c;i++)cout<<r[i]<<' ';
i_ak ioi;
}
明显过不了样例,并且我下载了测试点,也没有可以过的,为什么AC了?
并且我还在代码中不小心多输出了一行 cout<<t<<endl;
这样为什么还能AC?