时间限制: 1 Sec 内存限制: 128 MB
提交 状态 题面
题目描述
Andi is getting married! He and his partner plan to have N children. To avoid any hassle in the future, Andi wants to decide all their children’s name in advance. Specifically, he wants each child to have a name which is lexicographically larger than any of his/her older siblings. Of course, his partner also agrees with this idea. String A is lexicographically larger than string B if and only if B is a prefix of A or there exists an index i where Ai > Bi and Aj = Bj for all j < i. Note that a proper name can be as short as one character, but it cannot be an empty string.
Life is good for Andi, until one day he told his soon-to-be-grandmother-in-law (i.e. his partner’s grandma) about this marriage plan. After learning that Andi plans to have N children with her granddaughter, she gave him N names to be used. Moreover, the ith name can only be used for the ith child.
After going through a long debate with her grandma, Andi came into an agreement: The ith child’s name should be a subsequence of the ith name her grandma gave. A string A is a subsequence of string B if A can be obtained by deleting zero or more characters from B without changing the remaining characters’ order, e.g., ABC is a subsequence of DAEBCCB, but EFG is not a subsequence of FABEGC.
Even though Andi dislikes the given list of names, he still wants to impress his partner by showing that he can satisfy both her grandma’s wish and his own desire (i.e. each child’s name is lexicographically larger than any of his/her older siblings). However, Andi wonders, what is the maximum possible total length of their children names?
For example, let N = 3, and the names given by his partner’s grandma are (KARIM, PARBUDI,CHANDRA).
Here are several example set of names which satisfies Andi’s desire:
[AR, BI, CRA] with a total length of 2 + 2 + 3 = 7.
[ARI, BUDI, CHANDRA] with a total length of 3 + 4 + 7 = 14.
[ARIM, ARUDI, CHANDRA] with a total length of 4 + 5 + 7 = 16.
[AIM, ARBUDI,CHANDRA] with a total length of 3 + 6 + 7 = 16.
Among all sets of names which satisfy Andi’s desire in this example, the maximum total length is 16. Note that there might be cases where valid set of names cannot be obtained. In such case, you should output -1.
For example, let N = 2 and the names given by his partner’s grandma are (ZORO; ANDI). In this example, all subsequences of the 2nd name are lexicographically smaller than all subsequences of the 1st name, thus,no possible valid set of names can be obtained.
输入
Input begins with a line containing an integer N (1≤N≤15) representing the number of children. The next N lines, each contains a string Si (1≤|Si|≤15) representing the ith name given by Andi’s soon-tobe-grandmother-in-law. Si contains only uppercase alphabets (Sij ∈ A-Z).
输出
Output contains an integer in a line representing the maximum possible total length of their children names,or -1 if no possible valid set of names can be obtained.
样例输入
3
KARIM
PARBUDI
CHANDRA
样例输出
16
暴力DP
dp[i][j] i表示第i个序列，j表示第i个序列的第j大子序列
dp[i][j]=max(dp[i][j-1],dp[i-1][k]+string[i][j].size())
k表示i-1列，第一个大于[i][j]的子序列
#pragma GCC optimize(3,"Ofast","inline")
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <queue>
#include <vector>
#include <map>
#include <cmath>
#include <stack>
#include <set>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int n;
string s[20];
vector<string> ss[20];
int dp[20][(1<<15)+10];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++){
cin>>s[i];
//cout<<s[i]<<endl;
int len = s[i].size();
ss[i].push_back("");
for(int j=0;j<len;j++){
int lenlen=ss[i].size();
for(int k=0;k<lenlen;k++){
ss[i].push_back(ss[i][k]+s[i][j]);
//cout<<"push"<<endl;
}
}
sort(ss[i].begin(),ss[i].end());
}
memset(dp,-0x3f3f,sizeof(dp));
//cout<<ss[1].size()<<endl;
for(int i=1;i<ss[1].size();i++){
dp[1][i]=max(dp[1][i-1],(int)ss[1][i].size());
//cout<<dp[1][i]<<' '<<1<<' '<<i<<endl;
}
//cout<<n<<endl;
for(int i=2;i<=n;i++){
//cout<<i<<endl;
int lenbe=ss[i-1].size();
int lenno=ss[i].size();
for(int j=1,k=0;j<lenno;j++){
while(k<lenbe&&ss[i-1][k]<ss[i][j]) k++;
dp[i][j]=max(dp[i][j-1],dp[i-1][k-1]+(int)ss[i][j].size());
//cout<<dp[i][j]<<' '<<i<<' '<<j<<endl;
}
}
int ans=dp[n][ss[n].size()-1];
if(ans<0) cout<<"-1"<<endl;
else cout<<ans<<endl;
return 0;
}
Moriarty Yang 