洛谷P1018乘积最大——区间DP
2024-10-20 05:20:01
题目: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 ;
}
最新文章
- frame和bounds
- NFA引擎匹配原理
- MVC5中,加载分部视图,常见的方式
- thinkPHP 接支付宝及时到账接口
- gen already exists but is not a source folder ZT
- 一些关于Block, ARC, GCD的总结
- [转]GLES 3.0 新特性
- 3、REST风格的URL
- cdh4
- jQuery each的实现与call方法的详细介绍
- centos6.4安装flashcache
- linux之uniq
- java反射中Method类invoke方法的使用方法
- 关于C/S框架网单表绑定,查询
- Java BitSet解决海量数据去重
- linux中如何使用终端裁剪图片?
- acm 2072
- CSS 小结笔记之滑动门技术
- PHP学习第一天
- mac下idea 13 在tomcat 7控制台乱码