정수 구분의 4[구간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]);
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【경쟁 프로 전형적인 90문】008의 해설(python)의 해설 기사입니다. 해설의 이미지를 봐도 모르는 (이해력이 부족한) 것이 많이 있었으므로, 나중에 다시 풀었을 때에 확인할 수 있도록 정리했습니다. ※순차적으로, 모든 문제의 해설 기사를 들어갈 예정입니다. 문자열...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.