TRZ_2007 的博客

TRZ_2007 的博客

题解 AT1124 【電卓ゲーム】

posted on 2019-08-02 17:21:57 | under 题解 |

Description

给你三个数,让你在其中放入加号或乘号,使得他们的和最大。

Solution

思路: $DP$
定义: $dp[i]$ 表示:目前已经放了 $i$ 个数的最小值。
那么这个状态如何转移过来呢?
很简单, $dp[i]$ 的值只能从 $dp[i-1]$ 中取得,我们只需要看看是 $dp[i-1]*a[i]$ 大还是 $dp[i-1]+a[i]$ 大,取最大值即可。

code

#include <bits/stdc++.h>
using namespace std;

const int N = 10;

int dp[N],a[N];

int main()
{
    for(int i=1;i<=3;i++) scanf("%d",&a[i]);
    for(int i=1;i<=3;i++)
        dp[i] = max(dp[i-1]+a[i],dp[i-1]*a[i]);
    printf("%d\n",dp[3]);
}

刚刚模拟赛只有100,很生气,于是切了这题解闷