題目大意：?給出一個長度為 n 的字符串，字符串中共有 k 種不同的字符，現(xiàn)在問刪除掉所有字符的最小操作數(shù)，對于每種字符需要確定一個先后順序，每次需要刪除掉當(dāng)前所有的這種字符才能去刪除下一種字符，而對于每一種字符的刪除，一段當(dāng)前字符組成的連續(xù)區(qū)間可以一起刪除，現(xiàn)在問最小操作數(shù)，注意一下，當(dāng)某段字符被刪除后，剩下的字符會進(jìn)行拼接
題目分析：訓(xùn)練時讀錯題了，以為是青蛙祖瑪那樣的刪除，然后看 n 那么小，覺得像是區(qū)間dp，就沒再糾結(jié)了（這個樣例給的也太水了吧，開局兩分鐘以為是簽到題，沖了一發(fā)，然后帶歪榜了，阿這）
其實(shí)是一道十分水的狀壓dp，因?yàn)椴煌淖址疃嘤?20 種，且需要確定一種最優(yōu)的先后順序進(jìn)行刪除，所以我們設(shè) dp[ i ] 為第 i 種狀態(tài)下，二進(jìn)制為 1 的字符已經(jīng)被刪除掉的最小花費(fèi)，答案顯然就是 dp[ ( 1 << k ) - 1 ] 了
簡單講一下如何轉(zhuǎn)移，假設(shè)當(dāng)前枚舉的狀態(tài)為 i ，對于已經(jīng)被刪除掉的字符就不用管了，對于沒有被刪除掉的字符，我們統(tǒng)計(jì)一下當(dāng)前狀態(tài)下，刪除掉每種字符的貢獻(xiàn)，然后擇優(yōu)轉(zhuǎn)移就好了，統(tǒng)計(jì)每種字符的貢獻(xiàn)實(shí)質(zhì)上就是統(tǒng)計(jì)當(dāng)前字符被分成了多少段不相鄰的區(qū)間
代碼： ?
#include<iostream>
#include<cstdio>
#include<string>
#include<ctime>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<stack>
#include<climits>
#include<queue>
#include<map>
#include<set>
#include<sstream>
#include<cassert>
#include<bitset>
#include<unordered_map>
using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=1e6+100;int dp[(1<<20)+100],id[150],cnt[25];char s[410];int main()
{
#ifndef ONLINE_JUDGE
// freopen("data.in.txt","r",stdin);
// freopen("data.out.txt","w",stdout);
#endif
// ios::sync_with_stdio(false);memset(id,-1,sizeof(id));memset(dp,inf,sizeof(dp));int n,k;scanf("%d%d",&n,&k); scanf("%s",s+1);int tot=0;for(int i=1;i<=n;i++)if(id[s[i]]==-1)id[s[i]]=tot++;dp[0]=0;for(int i=0;i<1<<k;i++){memset(cnt,0,sizeof(cnt));int pre=-1;for(int j=1;j<=n;j++){if(((i>>id[s[j]])&1)==0&&pre!=id[s[j]]){pre=id[s[j]];cnt[pre]++;}}for(int j=0;j<k;j++)dp[i|(1<<j)]=min(dp[i|(1<<j)],dp[i]+cnt[j]);}printf("%d\n",dp[(1<<k)-1]);return 0;
}
