bzoj1260，懶得復(fù)制，戳我戳我

Solution:

這種題目我不會(huì)做qwq，太菜了
區(qū)間打牌(dp)

• 用f[l][r]表示從l到r最少需要染幾次色。

• 狀態(tài)轉(zhuǎn)移方程：

  1.\(f[l][r]=min(f[l][i],f[i+1][r]) (l<=i<r)\) 這段染色等于倆段分別染色，很好看出來(lái)。
  2.\(if(s[l]==s[r]) f[l][r]=min(min(f[l+1][r],f[l][r+1]),f[l+1][r-1])\)。

• 分倆種一可以直接涂上倆端點(diǎn)，2是可以忽略掉左端點(diǎn)和右端點(diǎn)。
• 第2點(diǎn)作用是很關(guān)鍵的，它會(huì)解決類似\(ABACDA\)之類的問(wèn)題。忽略掉一段端點(diǎn)之后就可以繼續(xù)找倆個(gè)端點(diǎn)進(jìn)行染色。

• 為什么是對(duì)的呢？因?yàn)樽詈鬅o(wú)論如何都一個(gè)節(jié)點(diǎn)都需要涂一次，所有的同色的端點(diǎn)就也被涂了。

轉(zhuǎn)載的博客

Code:

//It is coded by Ning_Mew on 5.22
#include<bits/stdc++.h>
using namespace std;const int maxn=55;int n;
string s;
int dp[maxn][maxn];int main(){cin>>s;n=s.length();memset(dp,0x5f,sizeof(dp));for(int i=0;i<n;i++){dp[i][i]=1;}for(int len=2;len<=n;len++){for(int i=0;i<=n-len;i++){int ss=i,tt=i+len-1;if(s[ss]==s[tt])dp[ss][tt]=min(dp[ss][tt-1],dp[ss+1][tt]);if(s[ss]==s[ss+1])dp[ss][tt]=min(dp[ss][tt],dp[ss+1][tt]);if(s[tt]==s[tt-1])dp[ss][tt]=min(dp[ss][tt],dp[ss][tt-1]);for(int k=ss;k<tt;k++)dp[ss][tt]=min(dp[ss][tt],dp[ss][k]+dp[k+1][tt]);}}printf("%d\n",dp[0][n-1]);return 0;
}

轉(zhuǎn)載于:https://www.cnblogs.com/Ning-Mew/p/9072844.html

總結(jié)

以上是生活随笔為你收集整理的【题解】 bzoj1260: [CQOI2007]涂色paint （区间dp）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。