题目链接

#include<cstdio>

#include<algorithm>

using namespace std;

int dp[305][305]={},jojo[305][305];

int t,kk;

int a[305];

void DFS(int x,int y,int toto){  //x左标记，y为右标记，toto表示目前你回溯到的层次

	if(x>=y)    //左标记在右标记右边，自然不成立 （剪枝）

		return ;

	if(toto==kk){// 如果你回溯到了kk的层次，那么就可以输出啦！

		printf("%d ",jojo[x][y]);

		t=1; //确保下次还进循环；

		return ;

	}

	DFS(x,jojo[x][y],toto+1);

	DFS(jojo[x][y]+1,y,toto+1);

}

int main(){

	int n;

	scanf("%d",&n);

	for(int i=1;i<=n;i++){

		scanf("%d",&a[i]);

	}

	for(int i=n-1;i>0;i--){

		for(int j=i+1;j<=n;j++){

			for(int k=i;k<j;k++){

				if(dp[i][j]<dp[i][k]+dp[k+1][j]+(a[i]+a[j])*a[k]){

					dp[i][j]=dp[i][k]+dp[k+1][j]+(a[i]+a[j])*a[k];  //合并时获得的价值就是  （ 1号金钥匙价值  +2号金钥匙价值）*  3号金钥匙价值。

					jojo[i][j]=k; //标记，方便后来回溯找输出队列；

				}

			}

		}

	}

	printf("%d\n",dp[1][n]);

	//开始回溯（开始吟唱！！！）

	t=1; //确保进入循环

	while(t){

		t=0;  //先将t的初值赋为0 ，如果找到了回溯的数，t就重新回1，如果t为零，那么回溯就完成了；

		kk++;

		DFS(1,n,1);

	}

	return 0;

}
巴特西

信奥赛一本通1573：分离与合体C++分离与合体

题目链接

最新文章

热门文章
