首页 > ACM题库 > HDU-杭电 > HDU 3539-Daizhenyang’s Letter[解题报告]HOJ
2014
11-05

HDU 3539-Daizhenyang’s Letter[解题报告]HOJ

Daizhenyang’s Letter

问题描述 :

One day, Daizhenyang is wandering in BUPT campus, thinking about having a girlfriend. Out of nowhere, a breath-taking beautiful girl came by, Daizhenyang was shocked by her beauty and was too stunned to say hi.
There’s an old saying, "Once there was true love for me but I did not cherish it. When it slipped away between my fingers, I began to regret. That is the saddest thing in life. If God could give me a second chance, I would tell the girl ‘I love you!’. If there should be a time limit on this love, I wish it would be 10000 years." Regretting is what Daizhengyang is being through. He wants to make everything right, so he figured out her mail address and decides to send a love letter.
After thinking again and again for a long time, Daizhenyang picked up some keywords to express his love and emotion. However, Daizhenyang is busy on his eternal lasting enterprise, unifying all kinds of ACM/ICPC problems to network flow, he wants to make this letter as short as possible. You can help him on this holy project, making his dream come true.

输入:

There are multiple cases in the input file.
For each test case:
Line 1: an single integer N ( 0<N<=12 ) , represents the number of keywords.
Line 2 – N+1: a keyword in each line, keywords only consist of uppercase letters ( for sincerity ) , length is less than 56.

输出:

There are multiple cases in the input file.
For each test case:
Line 1: an single integer N ( 0<N<=12 ) , represents the number of keywords.
Line 2 – N+1: a keyword in each line, keywords only consist of uppercase letters ( for sincerity ) , length is less than 56.

样例输入:

3
BUPT
TALENT
DAIZHENYANG
3
LOVE
VERY
RYTHM

样例输出:

Case #1: BUPTALENTDAIZHENYANG
Case #2: LOVERYTHM

#include <map>
#include <set>
#include <list>
#include <queue>
#include <cmath>
#include <stack>
#include <bitset>
#include <cstdio>
#include <cctype>
#include <vector>
#include <string>
#include <sstream>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;
#define lowbit(x) (x&(-x))
#define ff first 
#define ss second 
#define all(c) c.begin(),c.end()
#define PB push_back
#define MP make_pair
#define SZ(a) ((int)a.size())
#define CC(a,b) memset(a,b,sizeof(a))
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define repe(i,a,b) for(int i=(a);i<=(b);i++)
#define reps(i,s) for(int i=0;s[i];i++)
#define repi(it,c) for(typeof(c.begin()) it=c.begin();it!=c.end();it++)
#define inf 0x7f7f7f7f
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define LL long long 
#define ULL unsigned long long
#define L(x) (x<<1)
#define R(x) (x<<1|1) 
#define maxn 15
#define maxm 505
#define mod 1000000007
#define fuck puts("fuck")
#define pause system("pause")
#define SQ(x) ((x)*(x))
const double eps=1e-6;
const double pi=acos(-1.0);
template<class Z>inline bool checkmax(Z &a,Z b){if(a==-1||a<b){a=b;return true;}return false;}
template<class Z>inline bool checkmin(Z &a,Z b){if(a==-1||a>b){a=b;return true;}return false;}
template<class Z>inline bool mymax(Z &a,Z b){if(a<b){a=b;return true;}return false;}
template<class Z>inline bool mymin(Z &a,Z b){if(a>b){a=b;return true;}return false;}
int cas=1; void printcase(){printf("Case #%d: ",cas++);}

int pre[maxn][maxn];
int dp[1<<maxn][maxn];
string str[maxn],a[maxn];
int n;
map<string,bool>hash;

void init() {
	CC(pre,0);
	CC(dp,-1);
	hash.clear();
}
void input() {
	int idx=0,m=0;
	rep(i,0,n) {
		string b;
		cin>>b;
		if(!hash[b]) {
			hash[b]=true;
			a[idx++]=b;
		}
	}
	n=idx;
	rep(i,0,n) {
		int flag=0;
		rep(j,0,n) {
			if(i==j) continue;
			if(a[j].find(a[i])!=a[j].npos) {
				flag=1; break;
			}
		}
		if(!flag) str[m++]=a[i];
	}
	n=m;
	sort(str,str+n);
}
void initpre() {
	rep(i,0,n) {
		rep(j,0,n) {
			if(i==j) continue;
			rep(k,0,SZ(str[i])) {
				int ii,jj;
				for(ii=k,jj=0;ii<SZ(str[i]);ii++,jj++) {
					if(str[i][ii]!=str[j][jj]) break;
				}
				if(ii==SZ(str[i])) {
					pre[i][j]=SZ(str[i])-k;
					break;
				}
			}
		}
	}
}
void solve() {
	int tol=(1<<n);
	rep(i,0,n) {
		dp[1<<i][i]=str[i].size();
	}
	rep(sta,0,tol) {
		rep(i,0,n) {
			if(dp[sta][i]==-1) continue;
			rep(j,0,n) {
				if(sta&(1<<j)) continue;
				checkmin(dp[sta|(1<<j)][j],dp[sta][i]+SZ(str[j])-pre[j][i]);
			}
		}
	}
	
	int mini=-1;
	rep(i,0,n) {
		if(dp[tol-1][i]==-1) continue;
		checkmin(mini,dp[tol-1][i]);
	}
	string ans="";
	string temp="";
	int sta=tol-1;
	int p=13;
	while(sta) {
		string a=temp;
		int idx=-1;
		
		rep(i,0,n) {
			if(dp[sta][i]+temp.size()-pre[p][i]==mini) {
				if(idx==-1) {
					idx=i;
					a=a.substr(0,a.size()-pre[p][i])+str[i];
				}
				else {
					string b=temp;
					b=b.substr(0,b.size()-pre[p][i])+str[i];	
					if(a>b) {
						a=b;
						idx=i;
					}
				}
			}
		} 
		temp=a;
		ans+=str[idx];
		p=idx;
		sta^=(1<<idx);
	}
	printcase();
	cout<<temp<<endl;
}
int main() {
	while(~scanf("%d",&n)) {
		init();
		input(); 
		initpre();	
		solve();
	}
}

  1. 题本身没错,但是HDOJ放题目的时候,前面有个题目解释了什么是XXX定律。
    这里直接放了这个题目,肯定没几个人明白是干啥

  2. 一开始就规定不相邻节点颜色相同,可能得不到最优解。我想个类似的算法,也不确定是否总能得到最优解:先着一个点,随机挑一个相邻点,着第二色,继续随机选一个点,但必须至少有一个边和已着点相邻,着上不同色,当然尽量不增加新色,直到完成。我还找不到反例验证他的错误。。希望LZ也帮想想, 有想法欢迎来邮件。谢谢