Pieces(상태 dp)

1783 단어 동적 기획상압
You heart broke into pieces.My string broke into pieces.But you will recover one day,and my string will never go back. Given a string s.We can erase a subsequence of it if this subsequence is palindrome in one step. We should take as few steps as possible to erase the whole sequence.How many steps do we need? For example, we can erase abcba from axbyczbea and get xyze in one step. InputThe first line contains integer T,denote the number of the test cases. Then T lines follows,each line contains the string s (1<= length of s <= 16).
T<=10.OutputFor each test cases,print the answer in a line.Sample Input 
2
aa
abb
Sample Output 
1
2

제목 대략:
한 번에 하나의 문자열을 삭제할 수 있는 문자열을 줍니다. 문자열의 모든 문자는 문자열에 연속적으로 존재하지 않습니다. 최소한 몇 걸음이 걸려야 모든 문자열을 삭제할 수 있는지 물어보십시오.
아이디어:
상태 dp
모든 메모열 상태를 미리 처리해야 합니다.
dp[i]가 i상태에 이르렀을 때 사용한 걸음수.
상태 이동 방정식 dp[j-st[k]]=min(dp[j]+1, dp[j-st[k]]);
코드:
#include 
#include 
#include 
using namespace std;
const int ma=18;
int st[1<0)//     
    {
        if(x&1)
        ss[i++]=s[ans];
        ans--;
        x>>=1;
    }
    ss[i]='\0';
    int l=strlen(ss);
    int j=l-1;
    for(i=0;i>t;
    getchar();
    while(t--)
    {
        gets(s+1);
        n=strlen(s+1);
        memset(dp,0x3f,sizeof(dp));
        dp[(1<=0;j--)//       
        {
            for(int k=0;k
JS 중국어 문자열 과 UTF - 8 인 코딩 문자열 의 상호 변환
기본 libraries 디렉터리 밖의파일 읽기

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage