【CF1238E】Keyboard Purchase(状压DP,贡献)
2024-10-07 14:43:17
题意:有m种小写字符,给定一个长为n的序列,定义编辑距离为序列中相邻两个字母位置差的绝对值之和,其中字母位置是一个1到m的排列
安排一种方案,求编辑距离最小
n<=1e5,m<=20
思路:刚开始不会算贡献,觉得一定要把具体的排列搞出来才能做
其实pos[s[i-1]]和pos[s[i]]之差可以看成字符s[i-1]和字符s[i]被选择的时间的差
也就是说只有一个没有被选,另一个被选的情况下每次都会累计这样的字母对数的贡献
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<ll,ll> Pll;
typedef vector<int> VI;
typedef vector<PII> VII;
//typedef pair<ll,ll>P;
#define N 200010
#define M 200010
#define fi first
#define se second
#define MP make_pair
#define pb push_back
#define pi acos(-1)
#define mem(a,b) memset(a,b,sizeof(a))
#define rep(i,a,b) for(int i=(int)a;i<=(int)b;i++)
#define per(i,a,b) for(int i=(int)a;i>=(int)b;i--)
#define lowbit(x) x&(-x)
#define Rand (rand()*(1<<16)+rand())
#define id(x) ((x)<=B?(x):m-n/(x)+1)
#define ls p<<1
#define rs p<<1|1 const int MOD=1e9+,inv2=(MOD+)/;
double eps=1e-;
int INF=1e9;
int inf=0x7fffffff;
int dx[]={-,,,};
int dy[]={,,-,}; char s[N];
int dp[<<],f[][]; int read()
{
int v=,f=;
char c=getchar();
while(c<||<c) {if(c=='-') f=-; c=getchar();}
while(<=c&&c<=) v=(v<<)+v+v+c-,c=getchar();
return v*f;
} int main()
{
int n=read(),m=read();
int S=(<<m)-;
scanf("%s",s+);
rep(i,,n)
{
int x=s[i-]-'a',y=s[i]-'a';
f[x][y]++;
f[y][x]++;
}
rep(i,,S) dp[i]=INF;
dp[]=;
rep(sta,,S-)
{
int t=;
rep(i,,m-)
{
if(sta>>i&) continue;
rep(j,,m-)
if(sta>>j&) t+=f[i][j];
} rep(i,,m-)
{
if(sta>>i&) continue;
dp[sta+(<<i)]=min(dp[sta+(<<i)],dp[sta]+t);
}
}
printf("%d\n",dp[S]);
return ;
}
最新文章
- java http工具类和HttpUrlConnection上传文件分析
- WPF
- 一篇博客理解Recyclerview的使用
- Codeforces Round #363 Fix a Tree(树 拓扑排序)
- 問題排查:F5啟動偵錯後所提示的錯誤 (1)
- Durandal介绍
- HADOOP namenode HA
- WCF分布式开发步步为赢(11):WCF流处理(Streaming)机制
- Visual Assist的破解与安装
- 1136. Parliament(二叉树)
- CentOS 7 +Nginx
- Android开机动画启动流程
- Android基础_BroadcastReceiver
- Linux查看非root运行的进程
- Mego开发文档 - 处理并发冲突
- django管理数据库之中文字符编码问题
- scala链接mysql
- 构建之法 chapter1 心得
- java四种权限修饰符(public >; protected >; (default) >; private)
- [Spark][Python]Mapping Single Rows to Multiple Pairs