【CF1082F】Speed Dial（动态规划）

时间：2020-12-26 23:53:39

【CF1082F】Speed Dial（动态规划）

题面

CF

洛谷

题解

把\(Trie\)树建出来之后发现就是一个树型\(dp\)，每个点会对于其父亲中第一个被标记的点产生贡献。

那么把第一个点压入状态。

设\(f[i][p][k]\)表示当前点\(i\)，其到根的链上第一个被标记的点是\(p\)，其子树内总共选了\(k\)个点的最小代价。

枚举儿子是选还是不选进行转移。

时间复杂度\(O(n^2k^2)\)

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

#define MAX 505

const int inf=1073741823;

inline int read()

{

	int x=0;bool t=false;char ch=getchar();

	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

	if(ch=='-')t=true,ch=getchar();

	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

	return t?-x:x;

}

struct Node{int son[10],v;}t[MAX];

int tot=1;

int n,K,ans=inf;char ch[MAX];

int f[MAX][MAX][12],dep[MAX];

void Insert(char *s,int w)

{

	int u=1,l=strlen(s+1);

	for(int i=1;i<=l;++i)

	{

		if(!t[u].son[s[i]-48])t[u].son[s[i]-48]=++tot;

		u=t[u].son[s[i]-48];dep[u]=i;

	}

	t[u].v+=w;

}

void cmin(int &x,int y){x=min(x,y);}

int Solve(int u,int ld,int p)

{

	if(~f[u][ld][p])return f[u][ld][p];

	int g[12];memset(g,63,sizeof(g));

	g[u==ld]=t[u].v*(dep[u]-dep[ld]);

	for(int i=0;i<=9;++i)

	{

		int v=t[u].son[i];if(!v)continue;

		int tmp[12];memset(tmp,63,sizeof(tmp));

		for(int j=0;j<=K;++j)

			for(int k=0;k+j<=K;++k)

				cmin(tmp[j+k],g[j]+min(Solve(v,ld,k),k?Solve(v,v,k):inf));

		for(int j=0;j<=K;++j)g[j]=tmp[j];

	}

	for(int i=0;i<=K;++i)f[u][ld][p]=g[p];

	return f[u][ld][p];

}

int main()

{

	n=read();K=read()+1;memset(f,-1,sizeof(f));

	if(n<K){puts("0");return 0;}

	for(int i=1;i<=n;++i)scanf("%s",ch+1),Insert(ch,read());

	for(int i=0;i<=K;++i)ans=min(ans,Solve(1,1,i));

	printf("%d\n",ans);

	return 0;

}

相关文章