首页 > ACM题库 > HDU-杭电 > HDU 1865 1sting-背包问题-[解题报告] C++
2013
12-23

HDU 1865 1sting-背包问题-[解题报告] C++

1sting

问题描述 :

You will be given a string which only contains ‘1’; You can merge two adjacent ‘1’ to be ‘2’, or leave the ‘1’ there. Surly, you may get many different results. For example, given 1111 , you can get 1111, 121, 112,211,22. Now, your work is to find the total number of result you can get.

输入:

The first line is a number n refers to the number of test cases. Then n lines follows, each line has a string made up of ‘1’ . The maximum length of the sequence is 200.

输出:

The output contain n lines, each line output the number of result you can get .

样例输入:

3
1
11
11111

样例输出:

1
2
8

#include<stdio.h>
#include<string.h>
int dp[10000005];
bool mark[35];
int n,i,j,m,pp,tmp,total;
double tt,p;
char c;
struct P
{
    int p[3],all;
}price[35];
int max(int a,int b)
{
    return a>b?a:b;
}
void init()
{
    int i;
    memset(mark,0,sizeof(mark));
    total=tt*100.0;
    for (i=0;i<=total;++i) dp[i]=0;
    for (i=1;i<=n;++i)
    {
        memset(price[i].p,0,sizeof(price[n].p));
        price[i].all=0;
    }
}
int main()
{
    while (scanf("%lf%d",&tt,&n))
    {
        if (n==0) break;
        init();
        for (i=1;i<=n;++i)
        {
            scanf("%d",&m);
            for (j=1;j<=m;++j)
            {
                scanf(" %c:%lf",&c,&p);
                pp=p*100.0;
                if (c=='A' || c=='B' ||c=='C')
                {
                    price[i].p[c-'A']+=pp;
                    if (price[i].p[c-'A']>60000) mark[i]=1;
                }
                else mark[i]=1;
            }
            price[i].all=price[i].p[0]+price[i].p[1]+price[i].p[2];
            if (price[i].all>100000) mark[i]=1;
        }
        for (i=1;i<=n;++i)
        {
            if (!mark[i])
            {
                for (j=total;j>=price[i].all;--j)
                {
                    dp[j]=max(dp[j],dp[j-price[i].all]+price[i].all);
                }
            }
        }
        printf("%.2lf/n",double(dp[total])/100);
    }
    return 0;
}

解题报告转自:http://blog.csdn.net/acm_davidcn/article/details/5976777


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

  2. 第二种想法,我想来好久,为啥需要一个newhead,发现是把最后一个节点一直返回到嘴上面这层函数。厉害,这道题之前没样子想过。