OI

【动态规划】最大的算式

补上昨天的题（

先是一个热身：

////题目描述////

键盘输入一个n(n<=100)位的由数字‘1’~‘9’组成的数字串，在串中加入m(m<=20)个加号，求出和最小的表达式的值

一开始想到区间DP那了（然而并不是

由于最后一个加号把表达式分为两部分，前面是一个有m-1个加号组成的表达式，右边是一个确定的数，这样的状态中最优的一定是左边表达式值最小的时候。

设Fij表示前i个字符加入j个加号的最优值

Fij=min{Fkj-1+Sk+1~i}

(1<=k<i<=n)

所以

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define inf 2147483647
char a[300];
int sum(int j,int k){
    int i,t=0,b=1;
    j--;k--;
    for(i=k;i>=j;i--){
      t+=(a[i]-'0')*b;
      b*=10;
    }
    return t;
}
int main(){
    FILE *fin;
    fin=fopen("in.txt","r");
    long long f[300][300]={0};
    long long n,m,t;
    int b;
    fscanf(fin,"%d%d",&n,&m);
    fscanf(fin,"%s",&a);
    int i,j,k;
    for(i=1;i<=n;i++)
      f[i][0]=sum(1,i);
    for(i=2;i<=n;i++)
      for(j=1;j<=m;j++){
        t=inf;
        f[i][j]=inf;
        for(k=1;k<i;k++){
          t=f[k][j-1]+sum(k+1,i);
          if(t<f[i][j])f[i][j]=t;
        }
      }
    printf("%d\n",f[n][m]);
    fclose(fin);
    system("pause");
    return 0;
}

做完这题，接下来的这道就简单了：

////题目描述////

最大的算式

源程序名 BIGEXP.??? (PAS,C,CPP)

可执行文件名 BIGEXP.EXE

输入文件名 BIGEXP.IN

输出文件名 BIGEXP.OUT

题目很简单，给出N个数字，不改变它们的相对位置，在中间加入K个乘号和N-K-1个加号，（括号随便加）使最终结果尽量大。因为乘号和加号一共就是N-1个了，所以恰好每两个相邻数字之间都有一个符号。例如：

N=5, K=2，5个数字分别为1、2、3、4、5，可以加成：

1*2*(3+4+5)=24

1*(2+3)*(4+5)=45

(1*2+3)*(4+5)=45

……

输入
输入文件共有二行，第一行为两个有空格隔开的整数，表示N和K，其中(2<=N<=15, 0<=K<=N-1)。第二行为 N个用空格隔开的数字（每个数字在0到9之间）。

输出
输出文件仅一行包含一个整数，表示要求的最大的结果

样例
BIGEXP.IN

5 2
1 2 3 4 5

BIGEXP.OUT

120

说明

(1+2+3)*4*5=120

收到第一题的启发，发现这题换汤不换药。因为乘法与加法同样满足其中一数大的值也大，所以当k-1个乘号的表达式确定后，最大值只与表达式的最大值有关。其实就是加号换乘号，按位权展开变成累加，所以动规的思路也是差不多的

这里仍然有个坑：上一题左右两边一定是由加号连接的，而此题可能不用乘号连接的，所以转移时还要取乘号连接（消耗一个乘号）和加号连接（不消耗乘号）两者的最大值。

设Fij表示前i位使用j个乘号的表达式的最大值

则Fij=max{F[k][j-1]*S[k+1][i],F[k][j]+S[k+1][i]}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<stdio.h>
#include<stdlib.h>
int num[20]={0};
long long sum(int a,int b){
    int i;
    long long t=0;
    for(i=a;i<=b;i++)
      t+=num[i];
    return t;
}
int main(){
    FILE *fin,*fout;
    fin=fopen("bigexp.in","r");
    fout=fopen("bigexp.out","w");
    int n,i,j,k,kk;
    long long t,t2,max;
    long long f[20][20]={0};
    fscanf(fin,"%d%d",&n,&kk);
    for(i=1;i<=n;i++)
      fscanf(fin,"%d",&num[i]);
    for(i=1;i<=n;i++)
      f[i][0]=sum(1,i);
    for(i=2;i<=n;i++)
      for(j=0;j<=kk;j++){
        max=0;
        for(k=1;k<i;k++){
          t=f[k][j-1]*sum(k+1,i);
          t2=f[k][j]+sum(k+1,i);
          if(t2>t)t=t2;
          if(t>max)max=t;
        }
        if(f[i][j]<max)f[i][j]=max;
      }
    fprintf(fout,"%lld",f[n][kk]);
    fclose(fin);
    fclose(fout);
    return 0;
}

P1018高精度版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN=45,MAXK=10;
struct num{
    char n[MAXN];
    int len;
};

inline int numcmp(num &a,num &b){
    if(a.len>b.len)return 1;
    if(a.len<b.len)return -1;
    for(int i=a.len-1;i>=0;i--)
        if(a.n[i]>b.n[i])return 1;
        else if(a.n[i]<b.n[i])return -1;
    return 0;
}

inline void mul(num &a,num &b,num &ans){
    int i,j,jw;
    num c;
    memset(c.n,0,sizeof(c.n));
    for(i=0;i<a.len;i++){
        jw=0;
        for(j=0;j<b.len;j++){
            c.n[i+j]+=a.n[i]*b.n[j]+jw;
            jw=c.n[i+j]/10;
            c.n[i+j]%=10;
        }
        c.n[i+j]=jw;
    }
    c.len=a.len+b.len;
    while(c.n[c.len-1]==0&&c.len>1)c.len--;
    ans=c;
}

inline void gnum(num &a){
    memset(a.n,0,sizeof(a.n));
    char t[MAXN];
    scanf("%s",t);
    a.len=strlen(t);
    int st=0;
    //while(t[st]=='0'&&st<a.len-1)st++;
    for(int i=st;i<a.len;i++)
        a.n[a.len-i-1]=t[i]-'0';
    a.len-=st;
}

inline void pnum(num &a){
    for(int i=a.len-1;i>=0;i--)
        printf("%d",a.n[i]);
    printf("\n");
}

inline void split(num &a,int st,int ed,num &to){
    memset(to.n,0,sizeof(to.n));
    to.len=0;
    for(int i=ed;i>=st;i--)
        to.n[to.len++]=a.n[a.len-i];
}

num f[MAXN][MAXK]={0};

int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    num t,o;
    gnum(o);
    int i,j,k;
    for(i=1;i<=n;i++){
        split(o,1,i,f[i][0]);
    }
    
    for(i=2;i<=n;i++)
        for(j=1;j<=m;j++){
            memset(f[i][j].n,0,sizeof(f[i][j].n));
            f[i][j].len=1;
            for(k=1;k<i;k++){
                split(o,k+1,i,t);
                mul(t,f[k][j-1],t);
                if(numcmp(t,f[i][j])>0)
                    f[i][j]=t;
            }
        }
    
    pnum(f[n][m]);
    return 0;
}