首页 > ACM题库 > HDU-杭电 > HDU 1709 The Balance-动态规划-[解题报告] C++
2013
12-21

HDU 1709 The Balance-动态规划-[解题报告] C++

The Balance

问题描述 :

Now you are asked to measure a dose of medicine with a balance and a number of weights. Certainly it is not always achievable. So you should find out the qualities which cannot be measured from the range [1,S]. S is the total quality of all the weights.

输入:

The input consists of multiple test cases, and each case begins with a single positive integer N (1<=N<=100) on a line by itself indicating the number of weights you have. Followed by N integers Ai (1<=i<=N), indicating the quality of each weight where 1<=Ai<=100.

输出:

For each input set, you should first print a line specifying the number of qualities which cannot be measured. Then print another line which consists all the irrealizable qualities if the number is not zero.

样例输入:

3
1 2 4
3
9 2 1

样例输出:

0
2
4 5

题目大意:

给N个砝码  和一个天平 求出【1,sum】之间不能称出来的重量

思路:

可以看做是01背包  选与不选   然后比01背包多一种状态  那就是还可以相减  在此取绝对值就可以了

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

int vis[10005];
int x[10005];
int dp[10005];
int abs(int x)
{
    return x<0?-x:x;
}
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        memset(vis,0,sizeof(vis));
        memset(dp,0,sizeof(dp));
        int sum=0,cnt=0;
        vis[0]=1;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&x[i]);
            sum+=x[i];
        }
        for(int i=1;i<=n;i++)
        {
            memset(dp,0,sizeof(dp));
            for(int j=0;j<=sum;j++)
            {
                if(vis[j])
                {
                    dp[j+x[i]]=1;
                    dp[abs(j-x[i])]=1;
                }
            }
            for(int j=0;j<=sum;j++)
            if(dp[j])vis[j]=1;
        }

        for(int i=1;i<=sum;i++)
        {
            if(!vis[i])cnt++;
        }

        bool first=false;

        printf("%d\n",cnt);

        for(int i=1;i<=sum;i++)
        {
            if(!vis[i])
            {
                if(!first)
                {
                    printf("%d",i);
                    first=true;
                }
                else printf(" %d",i);
            }
        }

        if(cnt)puts("");
    }
}

解题报告转自:http://blog.csdn.net/u010709592/article/details/16832965


  1. #!/usr/bin/env python
    def cou(n):
    arr =
    i = 1
    while(i<n):
    arr.append(arr[i-1]+selfcount(i))
    i+=1
    return arr[n-1]

    def selfcount(n):
    count = 0
    while(n):
    if n%10 == 1:
    count += 1
    n /= 10
    return count

  2. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  3. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术,也不懂什么是算法,从而也不要求程序员懂什么算法,做程序从来不考虑性能问题,只要页面能显示出来就是好程序,这是国内的现状,很无奈。