网站在线备案,网站建设专业名词,项目免费推广平台,广州免费拍卖公司链接#xff1a;Iroha Loves Strings - AtCoder arc058_d - Virtual Judge
利用bitset这一数据结构#xff0c;定义bitset类型的变量dp[i]表示第i到n个字符串能拼成的字符串长度都有哪些#xff0c;比如00100101#xff0c;表示能拼成的长度有0,2,5#xff0c;#xff0…链接Iroha Loves Strings - AtCoder arc058_d - Virtual Judge
利用bitset这一数据结构定义bitset类型的变量dp[i]表示第i到n个字符串能拼成的字符串长度都有哪些比如00100101表示能拼成的长度有0,2,5注意bitset中的元素从右往左看下标从0开始利用递推关系更新dp[i]如下 dp[i] dp[i1] | (dp[i1] s[i]的长度) 若dp[i][k] 1说明第i到第n个字符串可以拼成长度为k的字符串 之后模拟取数i从1到k进行遍历每次取当前能取的最小的字符具体实现方式如下以下描述建议结合代码看 定义候选对数组 pairint,int sel[i][j]i为0或1用作开关变量j是候选对象的编号从1到cnt或ncnt每个sel[i][j]中存的是 候选字符所在的字符串的序号候选字符在该字符串中的下标 第一个字符的候选字符串i要满足dp[i1][k-s[i]的长度] 1也就是选了第i个字符串后之后的字符串必须保证能拼成(k-s[i]的长度)的长度的字符串将pairi,0加入sel i从1到k遍历每次在所有候选字符中选择字典序最小的那个字符作为答案接着分情况讨论 1.如果字符串还没用完就继续将该字符串的下一个元素加入候选队列如果有这样的字符串 ab和ac那么b和c都应该加入候选队列
2.如果有一个字符串用完了可能出现这样的情况abc abc这时应该先选前面的“abc”因为选完编号为i的字符串后新入选的字符串的下标从 i1 开始如果选了第二个或后面的就会有字符串没法被用到从而导致丢失解或错误解新入选的字符串编号为 j 要满足dp[ j1 ][ k-i-新字符串的长度 ]等于1这样选其能确保最终构成的字符串有可能长度为k将pair新字符串的编号0加入sel中
复杂度估计nk
注意
bitset和pair定义的先后会影响程序运行对错正确的顺序是先定义bitset后定义pair原因涉及到C语言本身
#includebits/stdc.h
using namespace std;const int maxn2005,maxk1e45;
char s[maxn][maxk];
int len[maxn];
int n,k;
bitsetmaxk dp[maxn];
pairint,int sel[2][maxn];//pair和bitset的先后问题int main()
{ios::sync_with_stdio(0);cin.tie(0);//freopen(D:\\in.txt,r,stdin);cinnk;for(int i1;in;i){cins[i];len[i]strlen(s[i]);}dp[n1][0]1;for(int in;i1;i--){dp[i](dp[i1] | (dp[i1]len[i]));}int cnt0;//挑出第一个字符的可选对象for(int i1;in;i){if(dp[i1][k-len[i]]){//printf(%d可选\n,i);sel[0][cnt]{i,0};}}int t1;for(int i1;ik;i){int ncnt0;t^1;char curz;for(int j1;jcnt;j){curmin(cur,s[sel[t][j].first][sel[t][j].second]);}coutcur;//更新下一组候选对象int minidn1;for(int j1;jcnt;j){int idsel[t][j].first,possel[t][j].second;if(s[id][pos]!cur) continue;if(poslen[id]-1){sel[t^1][ncnt]{id,pos1};}else{minidmin(minid,id); //选序号最小的这样后面的字符串还能用得上不然会白白浪费字符串}}for(int jminid1;jn;j){if(k-i-len[j]0 dp[j1][k-i-len[j]]){sel[t^1][ncnt]{j,0};}}cntncnt;}return 0;
}
