Problem Address:http://acm.zjut.edu.cn/ShowProblem.aspx?ShowID=1283
这道题做题做了一次,但是第一次是OLE,第二次是RTE。
当时思路可能也有点乱,所以没再继续。
今天看了一道类似的,说是背包问题,感觉不太像。看到一份解题报告感觉很相似,感觉昨天可能有点小细节没注意,所以回过头又做了一遍。
打了一次,DEBUG之后提交上去,RTE。
马上翻找昨天看到的一篇文章,说RTE一般是数组下标越界。
想了一下把第二个数组调的跟第一个一样大。结果还是RTE。
我说怎么会呢?100*100就是一万啊,我都开到1005了……
发现那个是千五= =
提交,AC。
也许昨天做的就是对的= =
结果出来各项数据都蛮好的,赞一下~
思路就是把每一个数跟之前所有的结果相加减,不过要注意记录是否是此次的加减结果。
如果是本次的结果则不能再运算,否则可以叠加运算。
这次用 i 记录是否是本次运算的结果。如果是则不对其运算。当把这个标志加进去的时候要注意本来的标志必须为零,否则不加此标志。
最后的数组出来后每个数对应的值应该是组成这个数的最小个数的和或差。
以下贴代码:
#include <iostream>
using namespace std;
int main()
{
int a[10005],num[10005];
int n,i,j,sum;
while(scanf("%d", &n)!=EOF)
{
sum = 0;
for (i=1; i<=n; i++)
{
scanf("%d", &num[i]);
sum += num[i];
}
for (i=1; i<=sum; i++)
{
a[i] = 0;
}
for (i=1; i<=n; i++)
{
if (a[num[i]]==0) a[num[i]] = i;
for (j=1; j<=sum; j++)
{
if (a[j]==0 || a[j]==i) continue;
if (j+num[i]>=1 && j+num[i]<=sum)
{
if (a[j+num[i]]==0) a[j+num[i]]=i;
}
if (j-num[i]>=1 && j-num[i]<=sum)
{
if (a[j-num[i]]==0) a[j-num[i]]=i;
}
if (num[i]-j>=1 && num[i]-j<=sum)
{
if (a[num[i]-j]==0) a[num[i]-j]=i;
}
}
}
n=0;
for (i=1; i<=sum; i++)
{
if (a[i]==0) num[n++]=i;
}
printf("%d/n", n);
if (n==0) continue;
for (i=0 ; i<n; i++)
{
if (i<n-1) printf("%d ", num[i]);
else printf("%d/n", num[i]);
}
}
return 0;
}