남양이공746 정수 구분(구간dp)

1316 단어 dp
제목:
하나의 수 n을 제시하고 m단으로 나누며 모든 단의 곱셈을 가장 높게 나누는 방법을 구합니다.
문제 풀이:
구간
상태: dp[i][j] 앞 j개의 점은 i단 곱셈의 최대치로 나뉜다.
여기에 정수 서열을 분해하는 함수가 하나 있는데, 스스로 써 보니 매우 간단하다.
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
#include<math.h>
using namespace std;
typedef long long lld;
#define oo 0x3f3f3f3f
#define maxn 210+5
lld dp[maxn][maxn];
lld dig[maxn][maxn];
int a[maxn];

int GetGig(lld n)
{
    lld temp=n,temp2,x=1;
    int len=0;
    while(temp)
    {
        len++;
        temp/=10;
        x*=10;
    }
    temp2=n;
    for(int i=1;i<=len;i++)
    {
        temp=temp2%x;
        for(int j=len;j>=i;j--)
        {
            dig[i][j]=temp;
            temp/=10;
        }
        x/=10;
    }
    return len;
}

int main()
{
    lld n,m;
    int T;
    scanf("%d",&T);
    while(T--)
    {
        cin>>n>>m;
        int len=GetGig(n);
        memset(dp,0,sizeof dp);
        for(int i=1;i<=len;i++)
            dp[1][i]=dig[1][i];
        for(int i=2;i<=m;i++)
            for(int j=i;j<=len;j++)
                for(int k=i-1;k<j;k++)
                    dp[i][j]=max(dp[i][j],dp[i-1][k]*dig[k+1][j]);
        cout<<dp[m][len]<<endl;
    }
	return 0;
}

좋은 웹페이지 즐겨찾기