UVa1630 Folding/poj 2176 Folding/zoj 1554 Folding

제목: 대문자로 구성된 열을 주고 가능한 한 짧은 열로 압축해야 하며, 압축을 끼워 넣을 수 있다.예를 들면 다음과 같습니다.
AAAAAAAAAABABABCCD -> 9(A)3(AB)CCD
NEERCYESYESYESNEERCYESYESYES -> 2(NEERC3(YES))
아이디어: DP[i][j].i, j는 각각 시작 위치, 끝 위치를 표시하고 이 단락이 압축된 길이를 저장한다.한 열의 가장 짧은 압축은 두 가지 상황이 있을 수 있다.그 자체가 중복되고 그 자체가 가장 짧게 압축된다.2. 두 단락으로 나누어 두 단락을 압축한 후 연결이 가장 짧다.
이 문제는 나를 오랫동안 곤경에 빠뜨렸다...그래도 이 문제에 감사하고 랜덤 데이터 생성, 파일 비교를 배웠습니다.계속 WA를 하기 때문에 나는 1000줄의 무작위 열을 만들어서 다른 사람의 프로그램과 비교했다.그리고 어쩔 수 없이 UVa의 데이터가 비교적 강해서 다른 OJ에서 했던 프로그램이 UVa에서 WA를 했는데 결국은 AC였다.

#include <iostream>  
#include <stdio.h>  
#include <cmath>  
#include <algorithm>  
#include <iomanip>  
#include <cstdlib>  
#include <string>  
#include <memory.h>  
#include <vector>  
#include <queue>  
#include <stack>  
#include <ctype.h>  
#define INF 1000000

using namespace std;

string str;
int DP[110][110];
string fold[110][110];

int judge(int l,int r){//         
	for(int i=1;i<=(r-l+1)/2;i++){
		if((r-l+1)%i)continue;
		bool flag=true;
		for(int j=l;j+i<=r;j++){
			if(str[j]!=str[j+i]){
				flag=false;
				break;
			}
		}
		if(flag)return i;
	}
	return false;
}

int fun(int l,int r){
	if(DP[l][r]!=-1)return DP[l][r];
	if(l==r){
		DP[l][r]=1;
		fold[l][r]=str[l];
		return 1;
	}
	int re=INF;
	//     
	int k;
	for(int i=l;i<r;i++){
		int tmp=fun(l,i)+fun(i+1,r);
		if(tmp<re){
			k=i;re=tmp;
		}
	}
	fold[l][r]=fold[l][k]+fold[k+1][r];
	re=fun(l,k)+fun(k+1,r);
	//      
	int len=judge(l,r);
	if(len){
		bool test=true;
		for(int i=l;i<=r;i++){//            
			if(str[i]=='('||str[i]==')')test=false;
		}
		char t[10];
    	sprintf(t,"%d",(r-l+1)/len);
    	string newstr=t+string("(")+fold[l][l+len-1]+string(")");
		if(test&&newstr.size()<re){
			re=newstr.size();
			fold[l][r]=newstr;
		}
	}
	//
	DP[l][r]=re;
	return re;
}

int main(){
	while(cin>>str){
		int R=str.size()-1;
		memset(DP,-1,sizeof(DP));
		fun(0,R);
		cout<<fold[0][R]<<endl;
	}
	return 0;
}