题意:
给一段字符串成段染色,问染成目标串最少次数.
SOL:
区间DP...
DP[i][j]表示从i染到j最小代价
转移:dp[i][j]=min(dp[i][j],dp[i+1][k]+dp[k+1][j]);
CODE:
BZ:
/*=================================================================
# Created time: 2016-03-28 21:10
# Filename: uva4394.cpp
# Description:
=================================================================*/
#define me AcrossTheSky
#include <cstdio>
#include <cmath>
#include <ctime>
#include <string>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm> #include <set>
#include <map>
#include <stack>
#include <queue>
#include <vector> #define lowbit(x) (x)&(-x)
#define FOR(i,a,b) for((i)=(a);(i)<=(b);(i)++)
#define FORP(i,a,b) for(int i=(a);i<=(b);i++)
#define FORM(i,a,b) for(int i=(a);i>=(b);i--)
#define ls(a,b) (((a)+(b)) << 1)
#define rs(a,b) (((a)+(b)) >> 1)
#define getlc(a) ch[(a)][0]
#define getrc(a) ch[(a)][1] #define maxn 500
#define maxm 100000
#define pi 3.1415926535898
#define _e 2.718281828459
#define INF 1070000000
using namespace std;
typedef long long ll;
typedef unsigned long long ull; template<class T> inline
void read(T& num) {
bool start=false,neg=false;
char c;
num=0;
while((c=getchar())!=EOF) {
if(c=='-') start=neg=true;
else if(c>='0' && c<='9') {
start=true;
num=num*10+c-'0';
} else if(start) break;
}
if(neg) num=-num;
}
/*==================split line==================*/
char A[maxn],C[maxn];
int dp[maxn][maxn],ans[maxn];
int main(){
freopen("a.in","r",stdin);
//while (scanf("%s",C)!=EOF){
scanf("%s",A);
//FORP(i,0,maxn) B[i]='';
int n=strlen(A);
memset(dp,0,sizeof(dp));
FORP(i,0,n-1)
FORP(j,i,n-1) dp[i][j]=INF;
FORP(i,0,n-1) dp[i][i]=1;
FORP(l,1,n-1)
FORP(i,0,n-1-l)
{
int j=i+l;
dp[i][j]=dp[i+1][j]+1;
FORP(k,i+1,j)
if (A[k]==A[i]) dp[i][j]=min(dp[i][j],dp[i+1][k]+dp[k+1][j]);
}
printf("%d",dp[0][n-1]);
//FORP(i,0,n-1)
// FORP(j,i,n-1) printf("%d%c",dp[i][j],j==n-1?'\n':' ');
/*memset(ans,0,sizeof(ans));
ans[0]=(A[0]!=C[0]);
FORP(i,1,n-1)
if (A[i]==C[i]) ans[i]=ans[i-1];
else {
ans[i]=dp[0][i];
FORP(j,0,i-1) ans[i]=min(ans[i],ans[j]+dp[j+1][i]);
}
printf("%d\n",ans[n-1]);
}*/
}
UVa:
/*=================================================================
# Created time: 2016-03-28 21:10
# Filename: uva4394.cpp
# Description:
=================================================================*/
#define me AcrossTheSky
#include <cstdio>
#include <cmath>
#include <ctime>
#include <string>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm> #include <set>
#include <map>
#include <stack>
#include <queue>
#include <vector> #define lowbit(x) (x)&(-x)
#define FOR(i,a,b) for((i)=(a);(i)<=(b);(i)++)
#define FORP(i,a,b) for(int i=(a);i<=(b);i++)
#define FORM(i,a,b) for(int i=(a);i>=(b);i--)
#define ls(a,b) (((a)+(b)) << 1)
#define rs(a,b) (((a)+(b)) >> 1)
#define getlc(a) ch[(a)][0]
#define getrc(a) ch[(a)][1] #define maxn 500
#define maxm 100000
#define pi 3.1415926535898
#define _e 2.718281828459
#define INF 1070000000
using namespace std;
typedef long long ll;
typedef unsigned long long ull; template<class T> inline
void read(T& num) {
bool start=false,neg=false;
char c;
num=0;
while((c=getchar())!=EOF) {
if(c=='-') start=neg=true;
else if(c>='0' && c<='9') {
start=true;
num=num*10+c-'0';
} else if(start) break;
}
if(neg) num=-num;
}
/*==================split line==================*/
char A[maxn],C[maxn];
int dp[maxn][maxn],ans[maxn];
int main(){
freopen("a.in","r",stdin);
while (scanf("%s",C)!=EOF){
scanf("%s",A);
//FORP(i,0,maxn) B[i]='';
int n=strlen(A);
memset(dp,0,sizeof(dp));
FORP(i,0,n-1)
FORP(j,i,n-1) dp[i][j]=INF;
FORP(i,0,n-1) dp[i][i]=1;
FORP(l,1,n-1)
FORP(i,0,n-1-l)
{
int j=i+l;
dp[i][j]=dp[i+1][j]+1;
FORP(k,i+1,j)
if (A[k]==A[i]) dp[i][j]=min(dp[i][j],dp[i+1][k]+dp[k+1][j]);
}
//FORP(i,0,n-1)
// FORP(j,i,n-1) printf("%d%c",dp[i][j],j==n-1?'\n':' ');
memset(ans,0,sizeof(ans));
ans[0]=(A[0]!=C[0]);
FORP(i,1,n-1)
if (A[i]==C[i]) ans[i]=ans[i-1];
else {
ans[i]=dp[0][i];
FORP(j,0,i-1) ans[i]=min(ans[i],ans[j]+dp[j+1][i]);
}
printf("%d\n",ans[n-1]);
}
}