最大乘积 动态规划.txt

包括计算几何、特殊数据结构、组合数学等知识点的代码。每个代码对应一道ACM试题

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
using namespace std;

//最大乘积 动态规划
#define NMAX 12
#define CMAX 7
__int64 f[NMAX][CMAX];//f[i][j],长度为i,用了j个乘号后的最大值
char str[22];

void print(int num,int k)
{	//用于调试时打印f[][]
    int i,j;
    for(i=0;i<num;i++)
    {
        for(j=1;j<=k;j++)
            printf("%6d",f[i][j]);
        cout<<endl;
    }
    cout<<endl;
//  system("pause");    
}

int conv(int start,int num)
{	//在str[i]中，以start为起点，num为长度所表示的数字
	int sum,i;
	sum=0;
	for(i=1;i<=num;i++)
	{
		sum*=10;
		sum+=str[start+i-1]-'0';
	}
	return sum;
}

void cal(int num,int chen)
{
	int i,j,temp,k;
	for(i=0;i<num;i++)
	{	//初始化，不用乘号时的情况
		f[i][0]=conv(0,i+1);
	}
	for(j=1;j<=chen;j++)
	{
		for(i=j;i<num;i++)
		{
			temp=0;
			for(k=0;k<i;k++)
			{
				//a1,a2,a3..an用j个乘号连接
				//看成是a1,a2...ak已经用j-1个乘号连接，
				//然后再与后面的ak+1,ak+2..an组成的数用1个乘号连接
				if(temp<f[k][j-1]*conv(k+1,i-k))
					temp=f[k][j-1]*conv(k+1,i-k);
			}
			f[i][j]=temp;//找到局部的最大乘积
		}
//		print(num,chen);
	}
}

int main()
{
	int num,chen;
	while(scanf("%d%d",&num,&chen)!=EOF)
    {
        scanf("%s",&str);
        cal(num,chen);
        printf("%I64d\n",f[num-1][chen]);
    }
	return 0;
}