欢迎来到Introzo百科
Introzo百科
当前位置：网站首页 > 技术 > Watch Later

Watch Later

日期：2023-09-27 13:43

Watch Later

题解：

状压DP。因为最多有K个不同的字符，那么就会有 2 k − 1 2^{k} - 1 2k−1种情况。
dp[i]表示的是在第i种状态，将i化成二进制，其中为1的已经成为最优解了，就是为1的已经被选取了，然后考虑剩下为0的。那么就是只有dp[i]，i的二进制全为1的时候是最优解。那么dp[(1< 

#include
#include
#include
using namespace std;
typedef long long ll;
typedef long double lf;
typedef pairP;
typedef unsigned long long ul;
const int inf = 0x3f;
const int N = 1e6+10;
const ll mod = 2012;
const double PI = 3.14;
const ul base = 131;int read(){char ch=getchar();int x=0,f=1;while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while('0'<=ch&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;
}
int random(int n){return(ll)rand()*rand()%n;}char s[405];
int id[405];
int dp[1<<21],num[405];int main(){//srand((unsigned)time(0));//freopen("out.txt","w",stdout);//freopen("in.txt","r",stdin);int n = read(),k = read();scanf("%s",s+1);int cnt = 0;for(int i = 1;i <= n;i++){if(id[s[i]-'a'] == 0){id[s[i]-'a'] = ++cnt;}//对不同的字符进行统计，并且对不同的字符进行标记。}for(int i = 0;i < (1<<21);i++){dp[i] = 100000000;}dp[0] = 0;for(int i = 0;i < (1<>(id[s[j]-'a']-1))&1) == 0){pre = id[s[j]-'a'];//假设i的二进制中为1的字符已经被处理了，所以这时候num[pre]++;//考虑二进制中为0的字符。一次统计其余每个字符 单独需要执行几次，保存在num数组}}for(int j = 1;j <= cnt;j++){//在dp[i]的基础上分别考虑再加上一个字符 的最小值dp[(1<<(j-1))|i] = min(dp[(1<<(j-1))|i],dp[i]+num[j]);}}cout<

相关文章

最近发表
猜你喜欢
晋ICP备2023019875号 | Introzo百科

关灯