동적 계획 의 최대 k 곱 하기

13987 단어 프로그래머
최대 k 곱 하기
문제 설명 설정 I 는 n 비트 10 진수 입 니 다.I 를 k 단 으로 나 누 면 k 개의 정 수 를 얻 을 수 있다.이 k 개의 정수 곱 하기 를 I 의 k 곱 하기 라 고 한다.주어진 I, n, k 에 대해 알고리즘 을 시험 적 으로 설계 하고 프로 그래 밍 으로 I 의 최대 k 곱셈 을 계산한다.
Intput
output
2 1
15
15
문제 분석
앞의 i 위 최대 j 곱 하기 기 는 dp [i] [j] 이 고, i 위 에서 낮은 j 위 까지 의 10 진 정 수 는 r [i] [j] 로 기록한다.dp [i] [j] 즉 앞 i 위 는 j 세그먼트 의 최대 곱 하기 (최 적 값) 로 나 뉜 다.
  • 가장 좋 은 서브 구조 증명: dp [i] [j] [마지막 단락 을 빼 면 dp [k] [j - 1] [j - 1] (k 는 i - 다음 단락 의 자릿수) * r [k + 1] [i]], 만약 에 dp [k] [[j - 1] [k] [j - 1] [j - 1]] [j - 1] [k] [j - 1], 양쪽 곱 하기 r [k + 1] [i] [k + 1] 즉 dp [k] [k] [k] [j - 1] [j - 1] * r [k + 1] [k] [j - 1]] [k + 1] [k]] [즉 dp] [j]]]] [j]]]]]] [j]]]]]] [j]]]]]]] [명제 가 맞지 않다.
  • 귀속 정의 dp [i] [j] = max (dp [k] [j - 1] * r [k + 1] [i]) j - 1 < = k < = i;k 는 마지막 단락 의 자릿수 를 없 애 는 것 을 나타 낸다
    • .
  • 재 귀 방식 으로 구 하 는 것 이 가장 좋 습 니 다. 앞 i 자리 최대 j 곱 하기 마지막 곱 하기 위 한 위 치 는 dp 로 기록 합 니 다.s[i][j];

    • 코드 부분
    #include
#include
using namespace std;
#define MAX 110

int r[MAX][MAX];
int dp[MAX][MAX];
int dp_s[MAX][MAX];

int traceback(int n,int k)
{
	if (k < 1)	return 0;
	traceback(dp_s[n][k], k - 1);
	cout << dp_s[n][k] << " ";
}

void matrix(int n,long long int count)
{
	for (int i = n; i >= 1; i--)
	{ 
		r[i][i] = count % 10;
		count /= 10;
	}
	for (int i = 1; i <= n; i++)
	{
		for (int j = i + 1; j <= n; j++)
		{
			r[i][j] = r[i][j - 1] * 10 + r[j][j];
		}
	}
}

int main()
{
	int n, k;
	long long int count;
	cout<<"  n     k     count："; 
	cin >> n >> k >> count;
	matrix(n, count);// r[i][j]   i   j ； 

	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= i; j++)
		{
			if (j == 1)
			{
				dp[i][j] = r[1][i];
				dp_s[i][j] = i;
			}
			for (int k = j - 1; k <= i; k++)
			{
				dp[i][j] = max(dp[i][j], dp[k][j - 1] * r[k + 1][i]);
				dp_s[i][j] = dp[i][j] > dp[k][j - 1] * r[k + 1][i] ? dp_s[i][j] : k;
			}
		}
	}
	
	
	cout<<endl<<"    ：" ;
	cout << dp[n][k];
	cout<<endl<<"    ：" ;
	traceback(n, k);
	system("PAUSE");
	return 0;
}
    matlab 연습 프로그램 (그레이스케일 이미지 최대 그레이스케일, 최소 그레이스케일, 평균 그레이스케일)
    [C언어] #3 포인터

    좋은 웹페이지 즐겨찾기

    개발자 우수 사이트 수집

    개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
    best100-homepage