2014
02-10

# 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
*/

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

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

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