(⊙o⊙)…，常規課考試又炸了！目測此次我要完蛋了...

又玩脫了，考數學的時候裝B裝大了！

算了，先進入正題...

題目描述：
Description
假設你有一條長度為5的木版，初始時沒有涂過任何顏色。你希望把它的5個單位長度分別涂上紅、綠、藍、綠、紅色，用一個長度為5的字符串表示這個目標：RGBGR。 每次你可以把一段連續的木版涂成一個給定的顏色，后涂的顏色覆蓋先涂的顏色。例如第一次把木版涂成RRRRR，第二次涂成RGGGR，第三次涂成RGBGR，達到目標。 用盡量少的涂色次數達到目標。
Input
輸入僅一行，包含一個長度為n的字符串，即涂色目標。字符串中的每個字符都是一個大寫字母，不同的字母代表不同顏色，相同的字母代表相同顏色。
Output
僅一行，包含一個數，即最少的涂色次數。

【樣例輸入1】RGBGR

【樣例輸出1】3

目測此題區間DP...貌似不是很惡心的樣子...(真是的，一個sb都過了！呃呃，一個猥瑣的矮子！)

算法解析：
f[i][j]表示從i位置到j位置染成滿足條件的顏色最少需要幾次。
當s[i]==s[j]時，f[i][j]=min(f[i+1][j],f[i][j-1])
當s[i]!=s[j]時，f[i][j]=min(f[i][k],f[k+1][j]) (i<=k<=j)

之后還要判斷當j-i==1 f[i][j]=1;

j-i!=1時f[i][j]=min(f[i][j],f[i+1][j-1]+1);(坑了我好久，一直等于1....)

之后就莫名其妙的Accept了...

#include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <ctime> #include <iostream> using namespace std; #define N 101 char s[N]; int dp[N][N]; int main() {scanf("%s",s);int n=strlen(s);memset(dp,0x3f,sizeof(dp));for(int i=1;i<=n;i++){dp[i][i]=1;}for(int l=1;l<n;l++){for(int i=1;i+l<=n;i++){int j=i+l;if(s[i-1]==s[j-1]){dp[i][j]=min(dp[i][j-1],dp[i+1][j]);if(l==1){dp[i][j]=1;}else{dp[i][j]=min(dp[i+1][j-1]+1,dp[i][j]);}}else{for(int k=i;k<j;k++){dp[i][j]=min(dp[i][k]+dp[k+1][j],dp[i][j]);}}}}printf("%d",dp[1][n]);puts(""); }

第二篇，希望大家多多支持！

?

轉載于:https://www.cnblogs.com/Winniechen/p/6601560.html

《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的BZOJ 1260：[CQOI2007]涂色paint的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。