首页 > ACM题库 > HDU-杭电 > hdu 2577 How to Type-动态规划-[解题报告]C++
2014
02-10

hdu 2577 How to Type-动态规划-[解题报告]C++

How to Type

问题描述 :

Pirates have finished developing the typing software. He called Cathy to test his typing software. She is good at thinking. After testing for several days, she finds that if she types a string by some ways, she will type the key at least. But she has a bad habit that if the caps lock is on, she must turn off it, after she finishes typing. Now she wants to know the smallest times of typing the key to finish typing a string.

输入:

The first line is an integer t (t<=100), which is the number of test case in the input file. For each test case, there is only one string which consists of lowercase letter and upper case letter. The length of the string is at most 100.

输出:

The first line is an integer t (t<=100), which is the number of test case in the input file. For each test case, there is only one string which consists of lowercase letter and upper case letter. The length of the string is at most 100.

样例输入:

3
Pirates
HDUacm
HDUACM

样例输出:

8
8
8

Hint
The string “Pirates”, can type this way, Shift, p, i, r, a, t, e, s, the answer is 8. The string “HDUacm”, can type this way, Caps lock, h, d, u, Caps lock, a, c, m, the answer is 8 The string "HDUACM", can type this way Caps lock h, d, u, a, c, m, Caps lock, the answer is 8

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

int a[25][1005];
int dp[25][1005];

int main()
{
    int tes;
    cin>>tes;
    while(tes--)
    {
        int n,m;
        cin>>n>>m;
        int i,j,k;
        for(i=1;i<=n;i++)
            for(j=1;j<=m;j++)
                scanf("%d",&a[i][j]);

        for(i=0;i<m;i++)
            dp[0][i]=-105;
        for(i=0;i<n;i++)
            dp[i][0]=-105;
        dp[0][1]=dp[1][0]=0;

        for(i=1;i<=n;i++)
            for(j=1;j<=m;j++)
            {
                dp[i][j]=max(dp[i-1][j],dp[i][j-1]);    //(x+1,y),(x,y+1)
                for(k=2;k<=m;k++)
                {
                    if(j%k==0)
                        dp[i][j]=max(dp[i][j],dp[i][j/k]);   //(x,y*k)
                }
                dp[i][j]+=a[i][j];
            }

        cout<<dp[n][m]<<endl;
    }
    return 0;
}

/*
1
3 8
9 10 10 10 10 -10 10 10
10 -11 -1 0 2 11 10 -20
-11 -11 10 11 2 10 -10 -10
*/
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

char str[105];
int dp[105][2];   //dp[i][1]表示完成i打印Cap灯亮,dp[i][0]表示完成i打印Cap灯灭

int main()
{
    int tes;
    cin>>tes;
    while(tes--)
    {
       cin>>str+1;
       int i;
       int len=strlen(str+1);
       dp[0][0]=0,dp[0][1]=2;   //初始状态为灯灭
       for(i=1;i<=len;i++)
       {
           if(str[i]>='A'&&str[i]<='Z')   //为大写
           {
               dp[i][1]=min(dp[i-1][1]+1,dp[i-1][0]+2);
               dp[i][0]=min(dp[i-1][1]+2,dp[i-1][0]+2);
           }
           else     //为小写
           {
               dp[i][0]=min(dp[i-1][0]+1,dp[i-1][1]+2);
               dp[i][1]=min(dp[i-1][0]+2,dp[i-1][1]+2);
           }
       }

       int res=min(dp[len][0],dp[len][1]+1);
       cout<<res<<endl;
    }
    return 0;
}

/*
3
Pirates
HDUacm
HDUACM
*/

解题转自:http://blog.csdn.net/coraline_m/article/details/18670803


  1. 为什么for循环找到的i一定是素数叻,而且约数定理说的是n=p1^a1*p2^a2*p3^a3*…*pk^ak,而你每次取余都用的是原来的m,也就是n

  2. 第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。

  3. “可以发现,树将是满二叉树,”这句话不对吧,构造的树应该是“完全二叉树”,而非“满二叉树”。

  4. Hello Web Admin, I noticed that your On-Page SEO is is missing a few factors, for one you do not use all three H tags in your post, also I notice that you are not using bold or italics properly in your SEO optimization. On-Page SEO means more now than ever since the new Google update: Panda. No longer are backlinks and simply pinging or sending out a RSS feed the key to getting Google PageRank or Alexa Rankings, You now NEED On-Page SEO. So what is good On-Page SEO?First your keyword must appear in the title.Then it must appear in the URL.You have to optimize your keyword and make sure that it has a nice keyword density of 3-5% in your article with relevant LSI (Latent Semantic Indexing). Then you should spread all H1,H2,H3 tags in your article.Your Keyword should appear in your first paragraph and in the last sentence of the page. You should have relevant usage of Bold and italics of your keyword.There should be one internal link to a page on your blog and you should have one image with an alt tag that has your keyword….wait there's even more Now what if i told you there was a simple WordPress plugin that does all the On-Page SEO, and automatically for you? That's right AUTOMATICALLY, just watch this 4minute video for more information at.