2013
12-23

# 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;
}

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