命运
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 7640 Accepted Submission(s): 2694
Problem Description
穿过幽谷意味着离大魔王lemon已经无限接近了！
可谁能想到，yifenfei在斩杀了一些虾兵蟹将后，却再次面临命运大迷宫的考验，这是魔王lemon设下的又一个机关。要知道，不论何人，若在迷宫中被困1小时以上，则必死无疑！
可怜的yifenfei为了去救MM，义无返顾地跳进了迷宫。让我们一起帮帮执着的他吧！
命运大迷宫可以看成是一个两维的方格阵列，如下图所示：
yifenfei一开始在左上角，目的当然是到达右下角的大魔王所在地。迷宫的每一个格子都受到幸运女神眷恋或者痛苦魔王的诅咒，所以每个格子都对应一个值，走到那里便自动得到了对应的值。
现在规定yifenfei只能向右或者向下走，向下一次只能走一格。但是如果向右走，则每次可以走一格或者走到该行的列数是当前所在列数倍数的格子，即：如果当前格子是（x,y），下一步可以是（x+1,y），(x,y+1)或者(x,y*k) 其中k>1。
为了能够最大把握的消灭魔王lemon，yifenfei希望能够在这个命运大迷宫中得到最大的幸运值。
可谁能想到，yifenfei在斩杀了一些虾兵蟹将后，却再次面临命运大迷宫的考验，这是魔王lemon设下的又一个机关。要知道，不论何人，若在迷宫中被困1小时以上，则必死无疑！
可怜的yifenfei为了去救MM，义无返顾地跳进了迷宫。让我们一起帮帮执着的他吧！
命运大迷宫可以看成是一个两维的方格阵列，如下图所示：
yifenfei一开始在左上角，目的当然是到达右下角的大魔王所在地。迷宫的每一个格子都受到幸运女神眷恋或者痛苦魔王的诅咒，所以每个格子都对应一个值，走到那里便自动得到了对应的值。
现在规定yifenfei只能向右或者向下走，向下一次只能走一格。但是如果向右走，则每次可以走一格或者走到该行的列数是当前所在列数倍数的格子，即：如果当前格子是（x,y），下一步可以是（x+1,y），(x,y+1)或者(x,y*k) 其中k>1。
为了能够最大把握的消灭魔王lemon，yifenfei希望能够在这个命运大迷宫中得到最大的幸运值。
Input
输入数据首先是一个整数C，表示测试数据的组数。
每组测试数据的第一行是两个整数n,m，分别表示行数和列数(1<=n<=20,10<=m<=1000)；
接着是n行数据，每行包含m个整数，表示n行m列的格子对应的幸运值K ( |k|<100 )。
每组测试数据的第一行是两个整数n,m，分别表示行数和列数(1<=n<=20,10<=m<=1000)；
接着是n行数据，每行包含m个整数，表示n行m列的格子对应的幸运值K ( |k|<100 )。
Output
请对应每组测试数据输出一个整数，表示yifenfei可以得到的最大幸运值。
Sample Input
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
Sample Output
52
hdu2571
题目大意：给你一幅地图，行走的时候可以有三种走法，如果当前格子是（x,y），下一步可以是（x+1,y），(x,y+1)或者(x,y*k) 其中k>1。问你从a[1][1]走到a[n][m]即从左上角走到右下角能够得到的最大值。
动态规划的思想是如果我们走的当前这一步如何能从前面的步骤中得到，
dp[i][j]=max(dp[i-1][j],dp[i][j-1],dp[i][j/k]);
题目地址：命运
AC代码：
#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
*/
How to Type
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 3068 Accepted Submission(s): 1412
Problem Description
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.
Input
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.
Output
For each test case, you must output the smallest times of typing the key to finish typing this string.
Sample Input
3 Pirates HDUacm HDUACM
Sample Output
8 8 8HintThe 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
hdu 2577
题目大意：给你一些字符串a~z||A~Z，然后我们按键最少能把他们都打出来，如果开始Cap大写灯是亮的，我们需要打a的话，可以按下cap键，然后再按a，需要两步，但是这下状态变为了大写灯亮，当然我们也可以按下shift，再按下a，需要两步，但是这下状态就变成了大写灯灭。题目要求的是，把这些字母打出来需要的最小按键数目。有一点需要注意，按键完成之后需要使cap键关闭。
解题思路：用dp[i][1]表示完成i打印Cap灯亮最小的步数,dp[i][0]表示完成i打印Cap灯灭的最小的步数，那么状态转移的时候dp[i][?]只能从dp[i-1][?]中转移，而且选小的，这样就好办了。
题目地址：How to Type
AC代码：
#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
*/