学佳澳杯 G 密码专家

区间dp

题目

样例及输出

1
32 40 17 40 35
13 19 7 3 5
11 41 42 6 17
47 21 42 35 23
20 45 36 16 42
5
addbd

88

思路

区间dp

我们规定字符串s[], 下标从1开始

1、一段区间 [i, j], 我们想要从s中删去这一段, 我们必须一个点、一个点的删去(因为题目说的)

2、我们假设s从开始到完全删去[i,j]这段字符串的过程最后一个字母是s[k]

3、那么我们可以 由 从s中删去[i,k] 和 从删去[k,j] 两个步骤推出 从s中删去[i,j] 。

准确来说, 删[i,k] 和 删[k,j] 是不存在任何交集的, 所以应该是由删去[i,k-1] 和删去[k+1, j] 推出 删去[i, j]

考虑区间dp

我们枚举区间长度l, 枚举它的起点i, (长度、起点确定, 终点可以确定), 再枚举它的中间点k, 即

dp[i][j] = min(dp[i][j], check(i, j, k)) ;

check函数是用 dp[i][k-1] 和dp[k+1][j] 计算 dp[i][j]

• 需要注意的是题目中 s[i] 换算成对应的权重比较特殊, 预处理一下会方便很多
• 数据不卡longlong, 开不开都一样

人畜无害的待码

#include <iostream>
#include <cstdio>
#include <cstring>
#define int long long 

using namespace std;

const int N = 300;

int n ;
int dp[N][N]; // 删掉<i,j>的最小代价 
int w[N][N];
char s[N];

int check(int i, int j, int k)
{
	/*
		return dp[i][k] + dp[k][j] + w[i-1][k] + w[j+1][k]
		但是需要考虑边界
	*/
	
	int ans = 0;
	if (k-1 >= i) ans += dp[i][k-1];
	if (k+1 <= j) ans += dp[k+1][j];
	
	if (i-1 >= 1) ans += w[s[i-1]][s[k]];
	if (j+1 <= n) ans += w[s[j+1]][s[k]];
	
	return ans;
}

void solve()
{
	
	for (int i=1;i <= 5;i ++ )
		for (int j=1;j <= 5;j ++ )
			scanf("%lld", &w[i][j]);
	
	scanf("%lld", &n);
	scanf("%s", s+1); // 下标从1开始 
	
	for (int i=1;i <= n;i ++ )
		s[i] = s[i] - 'a' + 1;	
        // 字母s[i]在abcde中的位置, dp时直接套w[] 

	memset(dp, 0x3f3f3f3f, sizeof dp);	// 方便取min 
	
	for (int l=1;l <= n;l ++ ) // 枚举长度 
	{
		for (int i=1;i <= n;i ++ )
		{
			int j = i+l-1;
			if (j > n) continue ;
			
			auto &u = dp[i][j];
			for (int k=i;k <= j;k ++ )
				u = min(u, check(i, j, k));
		}
	}
}

signed main()
{
	int T=1; scanf("%d", &T);
	while (T -- ) 
	{
		solve();
		printf("%lld\n", dp[1][n]);
	}
	
    return 0;
}