题目:https://www.luogu.org/problemnew/show/P1018

区间DP+高精,注意初始化和转移的细节。

代码如下:

#include<iostream>
#include<cstdio>
#include<cstring>
#define MAXN 20005
using namespace std;
typedef long long ll;
ll n,k,a[],f[][][MAXN],tmp[MAXN],num[MAXN];
char dc[];
void nm(ll l,ll r)
{
// printf("l=%lld r=%lld\n",l,r);
num[]=r-l+;
for(ll i=l;i<=r;i++)//正存即可
num[i-l+]=a[i];
// for(int i=1;i<=num[0];i++)printf("%lld",num[i]);
// cout<<endl;
}
void init()
{
a[]=strlen(dc);
for(ll i=;i<=a[];i++)
{
a[i]=dc[a[]-i]-'';
// memset(num,0,sizeof num);
// nm(1,i);
memcpy(f[i][],f[i-][],sizeof f[i-][]);//注意初始化!
f[i][][]++;f[i][][i]=a[i];
}
}
void ch(ll a[],ll b[])
{
tmp[]=a[]+b[]-;
for(ll i=;i<=a[];i++)
for(ll j=;j<=b[];j++)
{
tmp[i+j-]+=a[i]*b[j];
tmp[i+j]+=tmp[i+j-]/;
tmp[i+j-]%=;
}
if(tmp[tmp[]+])tmp[]++;
}
bool com(ll a[],ll b[])
{
if(a[]>b[])return ;
if(a[]<b[])return ;
for(ll i=a[];i;i--)
{
if(a[i]>b[i])return ;
if(a[i]<b[i])return ;
}
return ;
}
void print(ll a[])
{
for(ll i=a[];i;i--)
printf("%lld",a[i]);
}
int main()
{
scanf("%lld%lld",&n,&k);
cin>>dc;
init();
// f[1][1][0]=1;f[1][1][1]=1;
for(ll i=;i<=n;i++)
for(ll l=;l<=min(i-,k);l++)
for(ll j=l;j<i;j++)//从l开始!!!
{
// f[i][l]=max(f[j][l-1]*num(j+1,i),f[i][l]);
memset(tmp,,sizeof tmp);
memset(num,,sizeof num);
nm(j+,i);
ch(f[j][l-],num);
if(com(tmp,f[i][l]))memcpy(f[i][l],tmp,sizeof tmp);
}
print(f[n][k]);
return ;
}

最新文章

  1. frame和bounds
  2. NFA引擎匹配原理
  3. MVC5中,加载分部视图,常见的方式
  4. thinkPHP 接支付宝及时到账接口
  5. gen already exists but is not a source folder ZT
  6. 一些关于Block, ARC, GCD的总结
  7. [转]GLES 3.0 新特性
  8. 3、REST风格的URL
  9. cdh4
  10. jQuery each的实现与call方法的详细介绍
  11. centos6.4安装flashcache
  12. linux之uniq
  13. java反射中Method类invoke方法的使用方法
  14. 关于C/S框架网单表绑定,查询
  15. Java BitSet解决海量数据去重
  16. linux中如何使用终端裁剪图片?
  17. acm 2072
  18. CSS 小结笔记之滑动门技术
  19. PHP学习第一天
  20. mac下idea 13 在tomcat 7控制台乱码

热门文章

  1. rtems 4.11 部分m4文件分析
  2. 安卓ADT离线安装
  3. 【转】Android7.0版本以上的手机Eclipse无法打出LogCat
  4. CI学习总结
  5. C - The C Answer (2nd Edition) - Exercise 1-1
  6. Android 六大存储
  7. 可展开的UITableView (附源码)
  8. EasyNVR H5无插件摄像机直播解决方案前端解析之:监控实时直播的四分屏的前端展示
  9. 【转载】基于注解的SpringMVC简单介绍
  10. 后端CORS解决跨域问题