博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
SGU 327 Yet Another Palindrome(状态压缩DP)
阅读量:6575 次
发布时间:2019-06-24

本文共 2512 字,大约阅读时间需要 8 分钟。

题目链接:

题意:给出n个字符串。构造一个串s使得s包含n个串以及n个串的反串且这n个串在s中是连续的。求s的最短长度。

思路:设f[i][j][k]表示已经在s中的串的集合为i最后一个串是j(其实是在两端的是j,一个是j的原串一个是j的反串)且前面的是j串的状态是k(k=0表示原串,k=1表示反串)。

#include 
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define max(x,y) ((x)>(y)?(x):(y))#define min(x,y) ((x)<(y)?(x):(y))#define abs(x) ((x)>=0?(x):-(x))#define i64 long long#define u32 unsigned int#define u64 unsigned long long#define clr(x,y) memset(x,y,sizeof(x))#define CLR(x) x.clear()#define ph(x) push(x)#define pb(x) push_back(x)#define Len(x) x.length()#define SZ(x) x.size()#define PI acos(-1.0)#define sqr(x) ((x)*(x))#define MP(x,y) make_pair(x,y)#define FOR0(i,x) for(i=0;i
=0;i--)#define DOW1(i,x) for(i=x;i>=1;i--)#define DOW(i,a,b) for(i=a;i>=b;i--)using namespace std;void RD(int &x){scanf("%d",&x);}void RD(i64 &x){scanf("%I64d",&x);}void RD(u32 &x){scanf("%u",&x);}void RD(double &x){scanf("%lf",&x);}void RD(int &x,int &y){scanf("%d%d",&x,&y);}void RD(i64 &x,i64 &y){scanf("%I64d%I64d",&x,&y);}void RD(u32 &x,u32 &y){scanf("%u%u",&x,&y);}void RD(double &x,double &y){scanf("%lf%lf",&x,&y);}void RD(int &x,int &y,int &z){scanf("%d%d%d",&x,&y,&z);}void RD(i64 &x,i64 &y,i64 &z){scanf("%I64d%I64d%I64d",&x,&y,&z);}void RD(u32 &x,u32 &y,u32 &z){scanf("%u%u%u",&x,&y,&z);}void RD(double &x,double &y,double &z){scanf("%lf%lf%lf",&x,&y,&z);}void RD(char &x){x=getchar();}void RD(char *s){scanf("%s",s);}void RD(string &s){cin>>s;}void PR(int x) {printf("%d\n",x);}void PR(i64 x) {printf("%I64d\n",x);}void PR(u32 x) {printf("%u\n",x);}void PR(double x) {printf("%.6lf\n",x);}void PR(char x) {printf("%c\n",x);}void PR(char *x) {printf("%s\n",x);}void PR(string x) {cout<
<
=f[st2][j][t]) continue; f[st2][j][t]=temp; pre[st2][j][t][0]=st1; pre[st2][j][t][1]=i; pre[st2][j][t][2]=k; } }}string DFS(int st,int i,int j){ int st1,i1,j1,L; string a,b; if(!pre[st][i][j][0]) { if(!j) return match(s[i],reverse(s[i])); return match(reverse(s[i]),s[i]); } else { st1=pre[st][i][j][0]; i1=pre[st][i][j][1]; j1=pre[st][i][j][2]; a=DFS(st1,i1,j1); b=s[i]; if(j) b=reverse(b); L=SZ(match(b,a))-SZ(a); return match(b,a)+reverse(b).substr(SZ(b)-L,L); }}void print(){ int Min=INF,i,j,st=(1<
=j) p[j++]=str; } n=j; FOR0(i,n) { FOR0(j,n) if(i!=j&&(p[j].find(p[i])!=string::npos||reverse(p[j]).find(p[i])!=string::npos)) { break; } if(j>=n) s[k++]=p[i]; } n=k; init(); DP(); print(); return 0;}

  

转载地址:http://hbgjo.baihongyu.com/

你可能感兴趣的文章
滑动侧边栏
查看>>
UIView layer 的对应关系
查看>>
新浪研发中心: Berkeley DB 使用经验总结
查看>>
windbg调试句柄泄露
查看>>
好好理解返回值引用
查看>>
理清文本编码
查看>>
实用linux命令
查看>>
mysql之 percona-xtrabackup 2.4.7安装(热备工具)
查看>>
CCF NOI1150 确定进制
查看>>
SpringBoot实战总汇--详解
查看>>
Windows 7,无法访问internet,DNS无响应
查看>>
2018年7月1日笔记
查看>>
尝试使用iReport4.7(基于Ubuntu Desktop 12.04 LTS)
查看>>
安装GIT(基于Ubuntu Desktop 12.04 LTS)
查看>>
动态规划:金矿模型
查看>>
子元素应该margin-top为何会影响父元素【转】
查看>>
AJAX 状态值(readyState)与状态码(status)详解
查看>>
BZOJ3668:[NOI2014]起床困难综合症(贪心)
查看>>
jQuery 中bind(),live(),delegate(),on() 区别
查看>>
C++编程中const和#define的区别
查看>>