蓝桥杯：最大的算式（爆搜 || DP）

http://lx.lanqiao.cn/problem.page?gpid=T294

题意：中文题意。

思路：1、一开始想的是，乘号就相当于隔板，把隔板插入到序列当中，同一个隔板的就是使用加法运算，然后求最大值。也没有证明这个想法的正确性就蒙头写了。然后第一个数据就错了，还是挺良心的可以看第一个数据，发现k==0的情况我的输出是0，然后特判一下就过了。不过这样的复杂度很爆炸的，枚举了隔板的位置，最坏的复杂度应该是C(7, 15)吧。

2、后来想着如果n=100的话那就炸了。看了下别人的思路，可以用DP。有点类似于区间DP。

dp[i][j]表示枚举到第i个数字，使用了j个乘号的时候最大的答案是多少。

dp[i][j] = max(dp[i][j], dp[k][j-1] * (sum[i] - sum[k])) . (k < i)

就相当于当前枚举的是第j组，然后乘上这一组的贡献，实际感觉和我上边的想法挺像的呀。不过我的复杂度爆炸了。

DFS

 1 #include <cstdio>
 2 #include <cstring>
 3 using namespace std;
 4 #define N 20
 5 typedef long long LL;
 6 int div[N], n, k;
 7 LL w[N], sum[N], ans;
 8 
 9 void solve() {
10     //for(int i = 1; i <= k; i++) printf("div[%d] : %d
", i, div[i]);
11     LL now = 1;
12     for(int i = 2; i <= k; i++) 
13         now = now * (sum[div[i]] - sum[div[i-1]]);
14     now = now * sum[div[1]] * (sum[n] - sum[div[k]]);
15     if(now > ans) ans = now;
16 }
17 
18 void dfs(int id) {
19     if(id == k + 1) { solve(); return ; }
20     for(int i = div[id-1] + 1; i < n - (k - id); i++) {
21         div[id] = i; dfs(id + 1);
22     }
23 }
24 
25 int main() {
26     scanf("%d%d", &n, &k);
27     for(int i = 1; i <= n; i++) scanf("%I64d", &w[i]), sum[i] = sum[i-1] + w[i];
28     ans = 0;
29     dfs(1);
30     if(k == 0) ans = sum[n];
31     printf("%I64d
", ans);
32 }

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 using namespace std;
 5 #define N 20
 6 typedef long long LL;
 7 LL dp[N][N], sum[N];
 8 
 9 int main() {
10     int n, x, w; scanf("%d%d", &n, &x);
11     for(int i = 1; i <= n; i++) scanf("%d", &w), sum[i] = sum[i-1] + w, dp[i][0] = sum[i];
12     for(int i = 1; i <= n; i++) {
13         for(int j = 1; j <= x; j++) {
14             if(i <= j) continue;
15             for(int k = 1; k < i; k++) {
16                 dp[i][j] = max(dp[i][j], dp[k][j-1] * (sum[i] - sum[k]));
17             }
18         }
19     }
20     printf("%I64d
", dp[n][x]);
21 }