C小加

厚德 博学 求真 至善 The bright moon and breeze
posts - 145, comments - 195, trackbacks - 0, articles - 0
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

Ural 1005 Stone Pilet NYOJ zb的生日 解题报告

Posted on 2011-12-09 20:44 C小加 阅读(1743) 评论(2)  编辑 收藏 引用 所属分类: 解题报告

NYOJ地址:http://acm.nyist.net/JudgeOnline/problem.php?pid=325
题意:

把所给出的石头分成两堆,使两堆的差最小。

思路:

这道题可以用01背包写。。也可以直接暴力。。。题上的数据范围决定了dp的效率没有暴力的高。。

代码:

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

int a[23];
int sumAll;
int def;
void DFS(int sum,int i)
{
    
if(i<0return;
    
int temp=abs(sumAll-2*sum);
    
if(def>temp) def=temp;
    DFS(sum
+a[i],i-1);
    DFS(sum,i
-1);
}


int main()
{

        
int n;
        cin
>>n;
    
        memset(a,
0,sizeof(a));
        
int i=0;
        sumAll
=0;
        def
=0x7fffffff-1;
        
for(;i<n;i++)
        {
            cin
>>a[i];
            sumAll
+=a[i];
        }

        DFS(
0,n-1);
        cout
<<def<<endl;




    

    
return 0;
}

 

Feedback

# re: Ural 1005 Stone Pilet NYOJ zb的生日 解题报告  回复  更多评论   

2011-12-16 22:57 by alafeizai
我写了个dp的,但是wa了,请问有什么比较特殊的测试用例吗?

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cstring>
#include <stdlib.h>

using namespace std;

int a[20];
int f[200003];
int total=0;

void calc(int n)
{
for(int i=0; i<n; i++)
{
for(int j=total/2-a[i]; j>=0; j--)
{
if(f[j] == 1)
{
f[j+a[i]]=1;
}
}
}
}

int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
memset(a,0,20);
memset(f,0,200003);
f[0] = 1;
total = 0;

for(int i=0; i<n; i++)
{
scanf("%d",&a[i]);
total+=a[i];
}

calc(n);

for(int i=total/2; i>=0; i--)
{
if(f[i]==1)
{
printf("%d\n",total-2*i);
break;
}
}

}

return 0;
}

# re: Ural 1005 Stone Pilet NYOJ zb的生日 解题报告  回复  更多评论   

2011-12-16 23:13 by C小加
清零的时候用这样的格式
memset(a,0,sizeof(a));
@alafeizai

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理