[NOIP2000TG/codevs1017] 곱하기 최대 문제풀이 보고서

곱하기 최대 NOIP2000TG/codevs1017 골드 엘리베이터 구분 dp
제목 설명Description
올해는 국제수학연맹이 확정한'2000-세계수학의 해'로 마침 우리나라의 유명한 수학자 화라경 선생의 탄생 90주년을 맞았다.화라경 선생의 고향인 강소성 금단에서 새로운 수학 지능 경연 대회를 조직하였는데, 당신의 좋은 친구인 XZ도 다행히 참가할 수 있었다.행사에서 사회자는 행사에 참가한 모든 선수에게 이런 문제를 냈다.
 
길이가 N인 숫자열이 설치되어 있어 선수에게 K개의 곱셈을 사용하여 그것을 K+1개 부분으로 나누어 이 K+1개 부분의 곱셈을 최대로 할 수 있도록 한다.
 
또한 진행자는 선수들이 문제의 뜻을 정확하게 이해할 수 있도록 다음과 같은 예를 들었다.
 
숫자열은 312이고 N=3, K=1의 경우 다음과 같은 두 가지 분법이 있습니다.
 
1)  3*12=36
2)  31*2=62
  
이때 제목의 요구에 부합되는 결과는 31*2=62이다
 
지금 당신의 친한 친구인 XZ가 정확한 답을 얻기 위해 프로그램을 설계하는 것을 도와주십시오.
설명 입력 Input Description
프로그램의 입력은 두 줄로 구성됩니다.
첫 번째 행에는 총 2개의 자연수 N, K(6≤N≤40, 1≤K≤6)
두 번째 행은 N 길이의 숫자 문자열입니다.
출력 설명 Output Description
결과는 입력에 비해 최대 곱셈 (자연수) 을 출력해야 하는 화면에 나타납니다.
샘플 Sample Input 입력
4  2
1231
샘플 출력 Sample Output
62
데이터 범위 및 프롬프트 Data Size & Hint
이 문제는 비교적 낡아서 데이터도 실제적으로 비교적 작기 때문에 롱롱으로 통과할 수 있다
【문제풀이 사고방식1:검색】
위에서 말한 바와 같이 본 문제는 비교적 낡고 데이터도 실제적으로 비교적 작기 때문에 검색은 충분히 통과할 수 있다(bl ⊙)
그럼 폭수로 하면 된다;이 k개의 곱셈이 수열에 놓인 어떤 위치를 매거하여 N의 여러 가지 상황을 얻어내고 각 상황의 값을 계산한 다음min을 하면 된다.
코드도 물이 많네요. 숫자를 처리할 때 귀찮아요. 디버깅을 하면 오류를 빨리 찾아낼 수 있어요.
【코드】

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
char s[100];
long long a[100],b[100],n,k,i,ans;

void work()//    
{
	long long i,j,kk=1,shu=0,mul=1;
	for (i=1;i<=k+1;++i)
	{
		kk=1;
		shu=0;
		for (j=a[i];j>a[i-1];--j)
		{
			shu+=(s[j]-48)*kk;
			kk*=10;
		}
		mul*=shu;
	}
	if (mul>ans) ans=mul;
}

void dfs(long long dep)
{
	long long r;
	if (dep==k+1)
	{
		work();
		return;
	}
	for (r=1;r<n;++r)//        
	  if (!b[r])
	  {
	  	a[dep]=r;
	  	b[r]=1;
	  	dfs(dep+1);
	  	b[r]=0;
	  }
	return;
}

[문제풀이 사고방식 2:dp] (정해)
codevs 엘리베이터의 분류는 구분형 dp입니다. 하지만 저는 그게 무슨 귀신인지 구체적으로 모르겠습니다. 아마도 단계를 구분하는 것일 것입니다.
f[i][k]는 전 i개수에 k개의 곱셈을 삽입하여 얻은 최우수값을 표시하고, a[i][j]는 i-j 이 단락의 숫자가 얼마인지 나타낸다.
상태 이동 방정식: f[i][k]=max(f[i][k], f[j][k-1]*10+a[j+1][i])(k<=j<=i)
경계값 f[i][0]=a[1][i](i<=n)
잘 알겠습니다. 여러분 스스로 이해해 주십시오.
【코드】

#include<iostream>
#include<cstdio>
#include<cstring>
long long s;
int n,k1,i,j,k;
int a[100][100];
long long f[100][100];

using namespace std;
int main()
{
	freopen("mul.in","r",stdin);
	freopen("mul.out","w",stdout);
	scanf("%d%d",&n,&k1);
	cin>>s;
	for (i=n;i>=1;--i)
	{
		a[i][i]=s%10;
		s/=10;
	}
	for (i=2;i<=n;++i)//         
	  for (j=i-1;j>=1;--j)
	    a[j][i]=a[j][i-1]*10+a[i][i];
	for (i=1;i<=n;++i)//   
	  f[i][0]=a[1][i];
	if (k1==0)
	{
		printf("%lld",f[n][0]);
		return 0;
	}
	for (k=1;k<=k1;++k)
	  for (i=k+1;i<=n;++i)
	    for (j=k;j<i;++j)
	      f[i][k]=max(f[i][k],f[j][k-1]*a[j+1][i]);
	printf("%lld",f[n][k1]);
	return 0;
}