数字串划分

淡淡的烟草味﹌ 2022-06-09 14:43 155阅读 0赞

## **[http://acm.njupt.edu.cn/acmhome/problemdetail.do?&method=showdetail&id=1882][http_acm.njupt.edu.cn_acmhome_problemdetail.do_method_showdetail_id_1882]**    ##

## **C. 数字串划分** ##

时间限制(普通/Java):1000MS/3000MS          运行内存限制:65536KByte  
总提交:13            测试通过:2

描述

给你连续的N个数字符，在其中插入K个乘号将它分成K+1个部分，找出一种分法，使得这K+1个部分的乘积能够为最大。

输入

程序的输入共有两行：  
    第一行是2个正整数N，K（6≤N≤40，1≤K≤6）  
    第二行是N个连续的数字符。

输出

输出所求得的最大乘积（一个自然数）。

样例输入

4  2  
1231

样例输出

提示

1\*2\*31=62

题目来源

BYK

思路：

动态规划。

设m(i,j,n) 为第i个元素到第j个元素中插入n个\*的最优解。

其中 1<=i<j<=N;

则m(i,j,0)=str(i,j) 即不插入\*最优解即为自身。

m(i,j,n) = max\{ m(i,k,q)\*m(k,j,n-1-q)  \}  其中 i<=k<j,表示\*插入k个元素之后，

那么还剩下n-1个\*，分成两个部分，前面有q个，后面有n-1-q个，

其中，0<=q<=n-1;

这是一个三维表。

//初始化
    cin >> K;
    cin >> N;
    cin >> str;
    
    for( int i=1; i<=N; i++)
    {
    	for( int j=i; j<N; j++)
    	{
    		m(i,j, 0) = substr(str,i,j); //提取str的第i个元素到第j个元素
    	}
    }
    
    for ( int n=0; n<=K; n++)
    {
    	for( int i=0; i<=N; i++)
    	{
    		for( int j=i; j<N; j++)
    		{
    			string biggest;
    			for( int k=i; k<j; k++)
    			{
    				for(int q=0; q<=n-1; q++)
    				{
    					string temp = multiply( m(i,k,q), m(k,j,n-1-q) );//字符串乘法。
    					if( temp > biggest )       //字符串比较
    						biggest = temp;
    				}	
    			}
    			m(i,j,n) = biggest;
    		}		
    
    	}
    }

设i,j,n都取最大，为40\*40\*6=9600个元素，大约10k个元素，每个元素最多100byte，空间消耗为1M。

一共有五层循环，

时间复杂度为O（N^3\*K^2)

大约180万次计算。

每次计算还有大数相乘，大数比较。

所以时间在1s内可能有点复杂。

以后有时间贴个代码。

[http_acm.njupt.edu.cn_acmhome_problemdetail.do_method_showdetail_id_1882]: http://acm.njupt.edu.cn/acmhome/problemdetail.do?&method=showdetail&id=1882