解题思路

问题分析

我们需要将 $L$ 个字母分配到 $K$ 个键上，使得在保持字母顺序的前提下，总按键代价最小。按键代价定义为每个字母的频率乘以其在键上的位置（即按键次数）。例如，键上的第一个字母按$1$次，第二个字母按$2$次，依此类推。

关键条件

1. 字母顺序不变：字母必须按照给定的顺序分配到键上，不能打乱顺序。
2. 键的分配规则：
   • 每个键可以分配任意数量的字母（至少$1$个）。
   • 字母在键上的位置必须连续递增（即如果当前字母和上一个字母在同一个键上，则其位置为上一个字母的位置$+1$；否则，位置重置为$1$）。
3. 最小化总代价：总代价是所有字母的频率乘以其位置的累加和。
4. 多解时的优先级：如果存在多个解的总代价相同，优先让后面的键分配更多的字母（即最大化最后一个键的字母数，然后是倒数第二个，依此类推）。

这是一个典型的分段最优化问题，可以使用动态规划$（DP）$来解决。

代码实现

#include <iostream>
#include <cstring>  
#include <climits> 
#define LL long long
#define INF 0x3f3f3f3f


const int maxn = 250100;
using namespace std;

LL w[110][110], dp[110][110];
int vis[110][110];
int num[110];
char s1[110], s2[110];

int main()
{
	int k;
	int kk = 0;
	int n, m;
	int i, j;
	cin >>k;
	while(k--)
	{
		kk++;
		cin >>n>>m;
		cin >>s1;
		cin >>s2;
		for(i = 1; i <= m; i++)
			cin >>num[i];
		for(i = 0; i < 100; i++)
			for(j = 0; j < 100; j++)
				dp[i][j] = INF;
		for(int i=0;i<110;i++)
			for(int j=0;j<110;j++)
				w[i][j]=0;
		for(i = 1; i <= m; i++)
			for(j = i; j <= m; j++)
				w[i][j] = w[i][j-1]+(j-i+1)*num[j];
		for(i = 1; i <= n-1; i++)
		{
			for(j = m; j >= 1; j--)
			{
				for(int p = 1; p < j; p++)
				{
					if(dp[i][j] > dp[i-1][p]+w[1][p]+w[p+1][j]-w[1][j])
					{
						dp[i][j] =dp[i-1][p]+w[1][p]+w[p+1][j]-w[1][j];
						vis[i][j] = p;
					}
				}
			}
		}
		int v[110];
		int x = n-1, y = m;
		int t = 0;
		while(x)
		{
			v[++t] = vis[x][y];
			x--;
			y = v[t];
		}
		cout<<"Keypad #"<<kk<<":"<<endl;
		v[t+1] = 0;
		for(i = t; i >= 1; i--)
		{
			cout<<s1[n-i-1]<<": ";
			for(j = v[i+1]+1; j <= v[i]; j++)
				cout<<s2[j-1];
			cout<<endl;
		}
		cout<<s1[n-1]<<": ";
		for(j = v[1]+1; j <= m; j++)
			cout<<s2[j-1];
		cout<<endl;
		cout<<endl;
	}
	return 0;
}