abc344_D - String Bags 题解

一个月没有碰 oi，感觉水平已经退化到负的了。来复健一下。

D - String Bags

link

题意：给你 \(n\) 组字符串组，按 \(1\) ~ \(n\) 的顺序，对于每组字符串组，可从中至多选一个字符串。求能否用所选串按顺序拼接成指定串，以及选取字符串的最小个数。

然后读完题发现是个 \(01\) 背包；对于第 \(i\) 组的串，考虑其中有无能拼接到选定的前 \(i-1\) 个串的某个末端，并且价值更优。

其他见代码注释解释。

#include<bits/stdc++.h>
using namespace std;
const int inf=1e9;
int m,n;
int f[110][110];
int tl,sl;
string t,s;
int main(){
	cin>>t;
	tl=t.size();
	for(int i=0;i<110;i++)
		for(int j=0;j<110;j++) f[i][j]=inf;
	f[0][0]=0;
	scanf("%d",&m);
	for(int i=0;i<m;i++){
		for(int j=0;j<110;j++) f[i+1][j]=f[i][j];//用前 i 个组的结果对 f[i+1][j] 进行更新
		scanf("%d",&n);
		while(n--){
			cin>>s;
			sl=s.size();
			for(int j=0;j+sl<=tl;j++){
				int ok=1;//这个循环判断，在这个位置接上该子串，能否构成目标串
				for(int k=0;k<sl;k++){
					if(s[k]!=t[j+k]){//匹配不上
						ok=0;
						break;
					}
				}
				if(ok) f[i+1][j+sl]=min(f[i+1][j+sl],f[i][j]+1);//01 背包的选择，更新；
			}
		}
	}
	if(f[m][tl]==inf) puts("-1");
	else printf("%d",f[m][tl]);
	return 0;
} 

另：出题人很好心的把正解写进了 title。