HDU_2577 How to Type(DP)

10007 단어 type
요 며칠 DP에 의해 붕괴될 것 같다!!!오늘 이 문제를 받아도 손을 댈 수가 없어서 고수의 생각을 물어서야 해냈다.
아이디어:
다른 그룹 on[],off[]을 엽니다.각각 Caps Lock 램프를 켜고 Caps Lock 램프를 끌 때의 최소 키 수를 나타냅니다.
    s[i]    :

  on[i]
= min{ on[i-1] + 1, off[i-1] + 2} // , shift+ ;

  off[i]
= min{ on[i-1] + 2, off[i-1] + 2} // , shift+ ;

s[i] :

  on[i]
= min{ on[i-1] + 2, off[i-1] + 2} // shift+ , ;

  off[i]
= min{ on[i-1] + 2, off[i-1] + 1} // , ;

My Code:
#include <iostream>
#include
<cstdio>
#include
<cstring>

using namespace std;

const int N = 107;

int on[N], off[N];
char s[N];

int main()
{
//freopen("data.in", "r", stdin);

int t, len, i;
scanf(
"%d", &t);
while(t--)
{
scanf(
"%s", s);

memset(on,
0, sizeof(on));
memset(off,
0, sizeof(off));

on[
0] = 1; len = strlen(s);

for(i = 1; i <= len; i++)
{
if(isupper(s[i-1]))
{
on[i]
= min(on[i-1]+1, off[i-1]+2);
off[i]
= min(off[i-1]+2, on[i-1]+2);
}
else
{
on[i]
= min(off[i-1]+2, on[i-1]+2);
off[i]
= min(off[i-1]+1, on[i-1]+2);
}
}
printf(
"%d
", off[len]);
}
return 0;
}

.

좋은 웹페이지 즐겨찾기