돌의 합병과 곱셈의 가장 큰 차이

우리는 돌을 병합할 때 구간(기점과 종점 포함)을 매거하고 단점을 매거한다.O(n^3)
합병의 순서에 따라 다른 결과가 발생하기 때문에 돌귀결은 마지막 합병의 대상을 규정할 수 없기 때문에 매거단점은
왼쪽 합병의 결과와 오른쪽 합병의 결과가 합병된 후에 우리가 열거한 단점을 마지막 합병의 대상으로 삼는다.그러나
그리고 우리가 합병할 때는 오른쪽의 합병 결과가 필요하다.그러니까 오른쪽 동네부터 처리해야 돼.
일반적으로 두 가지 방법으로 처리됩니다.
1: 시작점을 일일이 열거할 때 거꾸로 열거하여 오른쪽의 구간이 처리되었는지 확인한다.
2: 종점을 일일이 열거하지 않고 크기를 일일이 열거하고 기점에 따라 종점의 위치를 계산하여 동네 간에 처리가 끝났음을 확보한다.
부착된 코드:

#include
#include
#include
#include
using namespace std;
int n,dp[2000][2000],dp2[2000][2000],sum[5000],num[5000],ans = -1,ans2 = 1e7;
int main()
{
    scanf("%d",&n);
    sum[0] = 0;
    memset(dp2,0x3f,sizeof(dp2));
    for(int i = 1;i <= n;i ++)
    {
        scanf("%d",&num[i]);
        sum[i] = num[i] + sum[i - 1];
        dp2[i][i] = dp2[n + i][n + i] = 0;
    }
    for(int i = 1;i < n;i ++)
        sum[n + i] = num[i] + sum[n + i - 1];
    n = (n<<1|1);
    for(int i = n;i >= 1;i --)// 
        for(int j = i;j <= n;j ++)// 
            for(int k = i;k < j;k ++)// 
            {
                dp[i][j] = max(dp[i][j],dp[i][k] + dp[k + 1][j] + sum[j] - sum[i - 1]);
                dp2[i][j] = min(dp2[i][j],dp2[i][k] + dp2[k + 1][j] + sum[j] - sum[i - 1]);
            }
    n >>= 1;
    for(int i = 1;i <= n;i ++)
    {
        ans = max(dp[i][n + i - 1],ans);
        ans2 = min(dp2[i][n + i - 1],ans2);
    }
    printf("%d
%d",ans2,ans);
}

곱셈이 가장 큰 가운데 곱셈이 교환율을 만족시키기 때문에 마지막에 누구를 곱해도 마찬가지다. 우리가 만약에 마지막 곱셈의 대상을 규정한다면 답안에 영향을 주지 않는다.
.그래서 우리는 오른쪽에 곱셈 연산을 하지 않고 왼쪽 구간의 최대 곱셈을 오른쪽의 구간으로 구성하는 것을 규정할 수 있다
세다이 수는 미리 처리된 것이다.그리고 우리는 단지 왼쪽의 합병 결과를 오른쪽의 이 수와 합병할 뿐이기 때문이다.그래서 저희가 필요해요.
조건은 1~i의 합병 결과일 뿐이므로 한 개의 들어올릴 필요가 없다.
부착된 코드:

#include
#include
#include
#include
using namespace std;
int num[45][45],n,k;
long long ji[45][15];
void read()
{
    int x = 1;
    char c;
    scanf("%c",&c);
    while(c < '0'||c > '9')
        scanf("%c",&c);
    while(c >= '0'&&c <= '9')
    {
        num[x][x] = c - '0';
        scanf("%c",&c);
        ++ x;
    }
    for(int i = n - 1;i >= 1;i --)
        for(int j = i + 1;j <= n;j ++)
            num[i][j] = num[i][j - 1] * 10 + num[j][j];
}
int main()
{
    scanf("%d %d",&n,&k);
    read();
    for(int i = 1;i <= n;i ++)
        ji[i][0] = num[1][i];
    for(int i = 1;i <= k;i ++)// 
        for(int b = i + 1;b <= n;b ++)// 
            for(int a = i;a < b;a ++)// 
                ji[b][i] = max(ji[b][i],ji[a][i - 1] * num[a + 1][b]);
    printf("%lld",ji[n][k]);
    return 0;
}

요약:
1: 만약에 어떤 구간을 합병해야 한다면 합병 구간을 할 때 우리는 맹목적으로 이 구간을 합병할 수 없다. 먼저 이 구간이
이전에 처리된 것으로 매거 순서나 매거 방식을 조정합니다.
2: 합병의 순서가 합병의 결과에 영향을 미치는지 관찰해야 한다. 만약에 합병의 순서가 합병의 결과에 영향을 미치지 않는다면 우리는 기점(또는 종점)을 열거하지 않고 마지막 합병의 수를 규정해야 한다. 그러면 우리는 불필요한 구역을 많이 처리하지 않을 것이다.