Gym101564H – Assembly line 题解

DP题目,第一反应是二维,一个表示开始区间一个表示结束。

然而,这样子的话,会出现最小花费合并后字母组合二次花费不一定全局最小的情况,所以其实要用三维dp,表示在一个区间上,合并成某个字母的最小花费。

状态转移方程dp[i][i+l][z] = min( dp[i][i+l][z] , dp[i][i+j][x]+dp[i+j+1][i+l][y]+cost[x][y] );

其中i代表区间的起始位置,l代表区间长度,j代表对这个区间进行划分的方案,x 代表前半段区间合并成的字母,y代表后半段区间合并成的字母,z代表x与y合并成 的字母,cost代表合并x与y的花费。

#include <bits/stdc++.h>

/* “江主席,代码AC吼不吼啊?吼啊!” “你们一定要梭我钦点你的程序TLE,我没有韧何的这个意思”
ZZZZZZZZZZZZZZ$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$
ZZZZZZZ$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$
$Z$$$$$$$$$$$$$$$$$$$$$$$$$$$$O8NNNNMNMNNNNNNNNZ$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$
$$$$$$$$$$$$$$$$$$$$$$$$$$$DNNNNNNNNNNNNNNNDDNNNNNNO$$$$$$$$$$$$$$$$$$$$$$$$$$$$
$$$$$$$$$$$$$$$$$$$$$$$$ONNNNNDNNNDDDDDDDDDD8DDD88NNDNZ7777777777$$77$$7$$$$$$$7
$$$$$$$$$$$$$$$$$77777ONNNNNDDDDDD8DD88O8888O88888D8DDDNO77777777777777777777777
$$$$$$$$$$$$$$7777777NNNNNNNDD8D8D8OOZZZZOZZ$ZZZOO88OOO8ND7777777777777777777777
$$$$$$77777777777777NNNNNDDNDD88OZOZZ77II777II7$$$$ZZ888O8DZ77777777777777777777
7777777777777777777NMNND8O888OZ$$$777III???????????7$$Z8D8DN87777777777777777777
777777777777777777DMMNN88OOZZZ$7$$777IIII???????????II7$88ODN$777777777777777777
77777777777777777$NMNND88ZZZZ$$7777IIII??????+++??????I7Z8O8DNIIIIIIIIIII7I7777I
7777777777777777INMMMNDOOZOOZ$$$77IIIII??+?+++++++++?I?I$ZODNNOIIIIIIIIIIIIIIIII
777777777IIIIIIIDMMMNNDD8ZZOZZ$$77I7IIII?????+=+++++???I7$ODNNNIIIIIIIIIIIIIIIII
77IIIIIIIIIIIIIIMMMMMNN8OZ8OOZ$7777IIII????+?+?++++++?I?I$ODNMNIIIIIIIIIIIIIIIII
IIIIIIIIIIIIIIIIMMMMMNNOOO88OZ$7777II???????????++++??III$O8NNDIIIIIIIIIIIIIIIII
IIIIIIIIIIIIIIIIMMMMMNDOO88OOZ$$77II??+???+?I?++++++??I??ZODNMZ????I????IIIIIIII
IIIIIIIIIIIIIIIIMMMMNMND88888OZZZ$$$7I+?I?+III???????III7$ODMM????????????????I?
IIIIIIII????????IMMMMNDD888NMDOZ$7$NN8II7??77I7$OO$II7III$ONMN??????????????????
II???????????????8MMMMMMNDMOOOZZZ$7I??7N$??NZ$$$7I?+?IIMN$DNNO??????????????????
?????????????????8DNNNDNNM88888ONONN8$7$MMMOOOODN8I7??IIMDDN8???????????????????
?????????????????O88DD888MO8OOOO$7I?O8O8MMMI$OOZZ7I$ZIIIZN$OO+++++++++++????????
???????????++++++88OO888OMZZZZ$$$$77$O8M$?7DI$77?++?III?$O7I7+++++++++++++++++++
?????++++++++++++78O888888O$$$7I$$777ON87?+M$7$$$7II????7I?II+++++++++++++++++++
++++++++++++++++++8O88888OMOZ$77IIIIZN8ZI?+?M77III??????NII7++++++++++++++++++++
++++++++++++++++++8O8888888O8M8$7$DNND8ZI?~??8I7$77??+$$III+++++++++++==++++++++
+++++++++++++++++=I8O888888O$7II??I8OZ88$7?I??DOO8OO$I??7??+====================
+++++++============OO8888888Z$777$888DMD8OOMNO++77I7II?II??=====================
===================OO88888888OZZZZ$ZZOOOZ??++++++IZ7777II++=====================
=====================88888888O8OOOZ$$I7I???+++??I77$7IIII+======================
=====================O888888Z$8O88OZ$$7I??+++??II7III?III~~~=~~~~~~~=~=~=======~
====================~O888888O$78DNDNDD8ZOZZ$$ZOZ$7IIIIIII~~~~~~~~~~~~~~~~~~~~~~~
==========~~~~~~~~~~~OO888888Z7Z88888Z7I?II??I?+?IIIIII7~~~~~~~~~~~~~~~~~~~~~~~~
=~~=~~~~~~~~~~~~~~~~~~88888888$$OZZZZ$77777I++++?II7II77~~~~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~~~~888888DD8$7OOZ$$$$777II????I77777:~~~~~~~~~~~~~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~~~:~NM8888DDD88$$Z$77III?+++????I7777:~::::::::::::::::::~~~~~~
~~~~~~~~~~~~~~::~:::MMM8D88DDDDD8ZZZ$777II??????I$$$I:::::::::::::::::::::::::::
~~~~~~~::::::::::::MMMMM8ZD8DDDDDD8OOO$$$777III$$ZZI::::::::::::::::::::::::::::
::::::::::::::=NMMMMMMMMMM7NDD8DDDDDDD8OOOOZOOZ$$$$I::::::::::::::::::::::::::::
::::::::::::NMMMMMMMMMMMMMM77D88DDDDD88DDDDDOZZZ$ZIMNDNO,::,,,,,,,,,,,,,::::::::
::::::::,?NNMMMMMMMMMMMMMMMM77I788D8O8888OOZ$Z$$77:NNNNNNNNN+,,,,,,,,,,,,,,,,,,,
:::::::MNNNNNMMMMMMMMMMMMMMMM77III7888OO8OZZ$7II.,:NNNNNNNNNNNND~,,,,,,,,,,,,,,,
::,NNNNNNNNNNNMMMMMMMMMMMMMMMM$IIII?I7OZ$7??++,..,:DNNNNNNNNNNNNNNNN+,,,,,,,,,,,
NNNNNNNNNNNNNNNNMMMMMMMMMMMMMMNZI?=~,...,7D7=....,:NNNNNNNNNNNNNNNNNNNND:,,,,,,,
NNNNNNNNNNNNNNNNNMMMNMMMMMMMMMNNI===:,,O$OIO88O.,::NNNNNNNNNNNNNNNNNNNNNNNNO,.,,
NNNNNNNNNNNNNNNNNMMMMNNNNMNMMNNNN=~~~NN8DZOO$$ND,,,DNNNNNNNNNNNNNNNNNNNNNNNNNN,.
NNNNNNNNNNNNNNNNNNMMNNNNNNNNNNNNNN=:DDONNNOZ8D8ZO,,8NNNNNNNNNNNNNNNNNNNNNNNNNNND
NNNNNNNNNNNNNNNNNNMMMNNNNNNMMNNNNNN,7OZNDNN8OD+ZZ$,DNNNNNNNNNNNNNNNNNNNNNNNNNNND
NNNNNNNNNNNNNNNNNNMMNNMNNNNNNNNNNNNN,Z7I8N8N88::,.$7NNNNNNNNNNNNNNNNNNNNNNNNNNND
NNNNNNNNNNNNNNNNNMMMNNNNNNNNNNNNNNNNN~O$INNNZO,,,,:$NNNNNNNNNNNNNNNNNNNNNNNNNNND
NNNNNNNNNNNNNNNNNMMMNNNNNNNNNNNNNNNNNO~8$NDN8O8,,,,ZNNNNNNNNNNNNNNNNNNNNNNNNNNND
NNNNNNNNNNNNNNNNNNMMMMMMMMMNNNNNNNNNNN~$NDN888O.:::Z8DNNNNNNNNNNNNNNNNNNNNNNNNND
“过92大寿也要按照基本法,去过。”  “当然蛤丝的代码是要TLE的” */

using namespace std;
int n,quest;
int dictCI[30],dictIC[205],cost_table[26][26][2];
int dp[205][205][26];
bool init=true;
int str_len,ans,ans_char;
int temp_char,temp_cost,right_cost,left_cost,right_b,left_b;
char temp_str[205];

int main()
{

	while (scanf("%d",&n))
	{
		if(!n)return 0;
		
		if(init) init=false;
		else printf("\n");
		
		memset(dictCI,0,sizeof(dictCI));
		memset(dictIC,0,sizeof(dictIC));
		memset(cost_table,0,sizeof(cost_table));
		
		for (int i=0;i<n;i++)
		{
			scanf("%s",temp_str);
			dictCI[temp_str[0]-'a']=i;
			dictIC[i]=temp_str[0];
		}
		for (int i=0;i<n;i++)
		{
			for (int j=0;j<n;j++)
			{
				scanf("%d-%s",&cost_table[i][j][0],temp_str);
				cost_table[i][j][1]=dictCI[temp_str[0]-'a'];
			}
		}
		scanf("%d", &quest);
		memset(dp,0,sizeof(dp));
		for(int ZhaoMM=1;ZhaoMM<=quest;ZhaoMM++)
		{
			scanf("%s",temp_str);
			str_len=strlen(temp_str);
			for (int i=0;i<str_len;i++) temp_str[i]=dictCI[temp_str[i]-'a'];
			for (int i=0;i<str_len;i++)
			{
				for(int j=0;j<str_len;j++) fill(dp[i][j],dp[i][j]+n,INT_MAX);
				dp[i][i][temp_str[i]]=0;
			}
			for(int i=1;i<str_len;i++)
			{
				for(int j=0;i+j<str_len;j++)
				{
					left_b=j;
					right_b=i+j;
					for(int k=left_b;k<right_b;k++)
					{
						for(int p=0;p<n;p++)
						{
							left_cost=dp[left_b][k][p];
							if(left_cost==INT_MAX) continue;
							for(int q=0;q<n;q++)
							{
								right_cost=dp[k+1][right_b][q];
								if(right_cost==INT_MAX) continue;
								temp_char=cost_table[p][q][1];
								temp_cost=cost_table[p][q][0];
								dp[left_b][right_b][temp_char]=min(dp[left_b][right_b][temp_char],left_cost+right_cost+temp_cost);
							}
						}
					}
				}
			}
			
			
			ans=INT_MAX;
			ans_char=0;
			for(int i=0;i<n;i++)
			{
				if(dp[0][str_len-1][i]<ans)
				{
					ans=dp[0][str_len-1][i];
					ans_char=i;
				}
			}
			printf("%d-%c\n",ans,dictIC[ans_char]);
			
			
		}
	}
}

留下你的评论呗...

电子邮件地址不会被公开。 必填项已用*标注