题意:

　　给一段字符串成段染色,问染成目标串最少次数.

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]);

	}

}

最新文章

  1. 饿了么基于Vue2.0的通用组件开发之路（分享会记录）
  2. C语言 经典编程100题
  3. 认真理解 图片 &lt;img&gt; background-image
  4. 使用HttpWebRequest和HtmlAgilityPack抓取网页（拒绝乱码，拒绝正则表达式）
  5. 第十三周学习笔记（编辑器选错了重发了这一个 原博客的确周天晚上提交了orz）
  6. poj 2635 千进制
  7. linux kernel.shmall shemax shemin 參數解釋
  8. 就Double、Decimal来说数据计算异常
  9. 浅谈Struts2(四)
  10. easyui tree使用方法
  11. js循环处理后台返回的json数组
  12. Oracle数据库各种名字的区别
  13. jQuery two way bindings（双向数据绑定插件）
  14. react表单的一些小例子
  15. Eclipse的Jar包解压出System.js里String与Boolean定义分号可有可无吗？
  16. web----粘包
  17. fft ocean注解
  18. 移动端H5混合开发设置复盘与总结
  19. 力扣（LeetCode）922. 按奇偶排序数组 II
  20. python基础之字符串常用操作总结

热门文章

  1. Unity Development with VS Code
  2. 全屏滚动效果H5FullscreenPage.js
  3. URL详解
  4. 7、I/O流
  5. WampServer数据库导入sql文件
  6. 配置php.ini实现PHP文件上传功能
  7. 非常简单的升级phpnow自带的php版本到5.3的方法
  8. 使用maven打包的注意事项
  9. 欧拉函数 - HDU1286
  10. word20161210