정수 구분의 4[구간dp]는 사고방식에 대해 설명한다

2036 단어 dp동적 기획
늙은이가 이야기하는 문제
두 개의 정수 n, m를 제시하고 n에 m-1개의 곱셈을 넣고 n을 m단으로 나누어 이 m단의 최대 곱셈을 구한다.
구간 dp:
사고방식: 먼저 n의 i~j 수위의 값을 구한다
m단의 상황을 분석하다
4자리의 수 정의 dp[i][j]는 i를 j단으로 나누는 최대 곱셈값을 설명하기 위해 보다 직관적으로 ij를 거꾸로 해서 여러분들이 잘 보실 수 있도록 하겠습니다.
         0        1         2       3 //       i
j 0    1        11      111    1111
  1    0        1         11      121
  2   0         0          0      0
  3  0            0         0      0
#include<bits/stdc++.h>
using namespace std;
long long dp[50][50];
long long  a[50][50];
char n[50];
int m;
void add(int x,int y)
{
    int k = 1;
    for(int i = y;i>=x;i--)
    {
        a[x][y]+=((n[i]-'0')*k);
        k*=10;
    }
}
int main()
{
        int t;
        scanf("%d",&t);
        while(t--)
        {
                scanf("%s%d",n,&m);
                memset(dp,0,sizeof(dp));
                memset(a,0,sizeof(dp));
                int L = strlen(n);
                for(int i = 0;i <L ;i++)
                {
                    for(int j = i;j < L;j++)
                    {
                        add(i,j);//        【i,j】
                    }
                }

            for(int i=0;i<L;i++)
                dp[i][0] = a[0][i];//dp【i】【j】   i      j               dp【i】【j】  a【i】【j】     
            m--;
            for(int j = 1; j <= m;j++)
            {
                for(int i = j;i <L;i++)
                {
                        for(int k = 0; k < i;k++)
                        {
                            dp[i][j] = max(dp[i][j],dp[k][j-1]*a[k+1][i]);//dp[1,2] = dp[0,1]*dp[1][2]
                        }
                }
            }
            for(int i = 0;i<L;i++)
            {
                for(int j = 0;j<L;j++)
                {
                    printf("%d ",dp[j][i]);
                }
                printf("
"); } printf("%lld
",dp[L-1][m]); } }

좋은 웹페이지 즐겨찾기