/*
Description：将n个整数相加的表达式添加 n-1 对括号，使得括号里运算的每一步的结果的总和最小.
Solution：DP，模拟
Author：uncleFun
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#define INF 199999999
int n ;
int s[21], dp[21][21], sum[21][21], a[21][21][80] ;
int str[21][21][80] ;
void init()
{
int i, j ;
memset(a, 0, sizeof(a)) ;
for(i = 1 ; i <= n ; i ++)
{
sum[i][i] = s[i] ;
str[i][i][1] = s[i] ;
str[i][i][0] = 1 ;
}
for(i = 1 ; i < n ; i ++)
for(j = i+1 ; j <= n ; j ++)
{
sum[i][j] = sum[i][j-1] + s[j];
dp[i][j] = INF ;
}
for(i = 1 ; i <= n ; i ++) dp[i][i] = 0 ;
}
void show(int x[])
{
for(int i = 1 ; i <= x[0] ; i ++)
if(x[i] == -1) printf("(") ;
else if(x[i] == -2) printf(")") ;
else if(x[i] == 0) printf("+") ;
else printf("%d", x[i]) ;
printf("\n") ;
}
void setStr(int l, int m, int r)
{
int i, j, len ;
str[l][r][1] = -1 ;
len = str[l][m][0] ;
for(i = 2 ; i <= len+1 ; i ++) str[l][r][i] = str[l][m][i-1] ;
str[l][r][i++] = 0 ;
len = str[m+1][r][0] ;
for(j = 1 ; j <= len ; j ++, i++) str[l][r][i] = str[m+1][r][j] ;
str[l][r][i++] = -2 ;
str[l][r][0] = i-1 ;
for(i = 1 ; i <= a[l][m][0] ; i ++) a[l][r][i] = a[l][m][i] ;
for(j = 1 ; j <= a[m+1][r][0] ; j ++, i ++) a[l][r][i] = a[m+1][r][j] ;
a[l][r][i] = sum[l][r] ;
a[l][r][0] = i ;
}
int DP()
{
int i, j, k, x ;
for(x = 1 ; x <= n ; x ++ )
for(i = 1 ; i < n ; i ++)
for(j = i+1 ; j <= n ; j ++)
for(k = i ; k < j ; k ++)
if(dp[i][j] > dp[i][k]+dp[k+1][j]+sum[i][j])
{
dp[i][j] = dp[i][k]+dp[k+1][j]+sum[i][j] ;
setStr(i, k, j) ;
}
return dp[1][n] ;
}
int main()
{
int i ;
while(~scanf("%d", &n))
{
for(i = 1 ; i <= n ; i ++) scanf("%d", &s[i]) ;
init() ;
int ans = DP() ;
show(str[1][n]) ;
printf("%d\n", ans) ;
for(i = 1 ; i <= a[1][n][0] ; i ++) printf("%d ", a[1][n][i]) ; printf("\n") ;
}
return 0 ;
}
5 条评论
-
hjxcpg LV 9 @ 2015-08-18 16:05:58
juruoshiwo
-
@ 2015-05-04 18:09:49
[b]呵呵[/b]
-
@ 2015-05-04 18:09:14
呵呵
**真的吗*
呵呵
hehe -
@ 2014-02-05 10:55:30
为什么你们都不看一下剪辑器快速入门呢？
这么好的东西你们不看
选中代码，然后一个tab健即可显示源代码！我不知道你的代码如何，但我也是错过来的。提几个醒
- 题目的数据是括号尽量靠后。例如数据是 3 2 2 2 ((2+2)+2)是错解 (2+(2+2))是正解
- 输出中间和的时候是按照从左到右，从里到外。这个左得注意了你打的括号的结束的位置，而不是按照开始的位置。
这是我的代码，可能不太怎么好
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#define max_n 20int sum[max_n+1];/*sum[i] Σa[i]*/
int min_s[max_n+1][max_n+1];
int min_mid[max_n+1][max_n+1];
int num[max_n+1];
int n;
struct node{
int dpth;
int v;
int val;
};
struct node mid_sum[max_n+1];
int mid_sum_r;void init()
{
int i;
scanf("%d",&n);
sum[0] = 0;
for (i = 1;i <= n;i++) {
scanf("%d",sum+i);
num[i] = sum[i];
min_s[i][i] = 0;
sum[i] += sum[i-1];
}
}void dp()
{
int u,l,v,mid,tt;
for (l = 1;l < n;l++) {
for (u = 1;u+l <= n;u++) {
v = l+u; //min_s[u][v]
mid = u+1;
min_s[u][v] = sum[v]-sum[u-1]+min_s[mid][v];//+min_s[u][mid-1]
min_mid[u][v] = mid;
for (mid = u+2;mid <= v;mid++)
if (min_s[u][v] >= (tt = sum[v]-sum[u-1]+min_s[u][mid-1]+min_s[mid][v])) {
min_s[u][v] = tt;
min_mid[u][v] = mid;
}
}
}
}void print_brckt(int u,int v,int dpth)
{
if (u == v) {
printf("%d",num[u]);
return;
}
mid_sum[mid_sum_r].val = sum[v]-sum[u-1];
mid_sum[mid_sum_r].v = v;
mid_sum[mid_sum_r++].dpth = dpth;
printf("(");
print_brckt(u,min_mid[u][v]-1,dpth+1);
printf("+");
print_brckt(min_mid[u][v],v,dpth+1);
printf(")");
}int cmp(const void *a,const void *b)
{
struct node *c,*d;
c = (struct node *)a; d = (struct node *)b;
if (c->v == d->v)
return d->dpth-c->dpth;
else
return c->v-d->v;
}int main()
{
int i;
init();
dp();
mid_sum_r = 0;
print_brckt(1,n,0);
printf("\n%d\n",min_s[1][n]);
qsort(mid_sum,mid_sum_r,sizeof(struct node),cmp);
for (i = 0;i < mid_sum_r-1;i++)
printf("%d ",mid_sum[i].val);
if (i < mid_sum_r) printf("%d\n",mid_sum[i].val);
return 0;
} -
@ 2013-03-19 21:47:08
选中所有代码，并按tab键可以制作一个代码块用于显示代码。
-
@ 2013-04-04 23:59:53
为什么作为设计者不想点别的?
-
@ 2013-04-06 17:18:41
似乎设计者是swx，mrw是日常维护？
-
@ 2013-04-06 17:50:26
团队成员都是设计者
我不知道这块的机构是不是就分的这么复杂
你，去设计，你，去写xx功能
和建筑工地似的
你，去搬砖，你，去倒水泥抱歉，打错位置了，竟然不可以删除。。。。。囧
-
- 1
