http://wikioi.com/problem/1017/

划分型动态规划
1.转移方程是:f[i][j]=max(f[k][j-1]*t[k+1][i]),f[i][j]表示前面i个字符加上j个乘号所得的最大值,t[i][j]表示i到j的数值;
2.可预处理,先计算出每段的数字值;
3.看代码分析错误实在不行时,还是debug一下吧。

#include <cstring>
#include <iostream>
#define ulong long long
using namespace std;
ulong t[45][45]; // number from i to j; start from 0;
ulong f[45][10]; // the first i digits, seperated to j part, max value;
int data[45] = {0}; int main()
{
int n, k;
cin >> n >> k;
memset(t, 0, sizeof(t));
memset(f, 0, sizeof(f));
// input
char c;
for (int i = 0; i < n; i++)
{
cin >> c;
data[i] = c - '0';
t[i][i] = data[i];
}
// pre-process
for (int i = 0; i < n; i++)
{
for (int j = i+1; j < n; j++)
{
t[i][j] = t[i][j-1]*10 + data[j];
}
}
// dp
for (int j = 0; j <=k ; j++)
{
for (int i = j+1; i <= n; i++)
{
if (j == 0)
{
f[i][0] = t[0][i-1];
}
else
{
ulong max = 0;
for (int x = 1; x < i; x++)
{
ulong tmp = f[x][j-1] * t[x][i-1];
if (tmp > max) max = tmp;
}
f[i][j] = max;
}
}
}
cout << f[n][k] << endl;
return 0;
}

  

最新文章

  1. Linux网络驱动--snull
  2. 浅谈在静态页面上使用动态参数,会造成spider多次和重复抓取的解决方案
  3. mysql 慢查询日志切割
  4. 360路由器刷openwrt后设置wifi中继
  5. C#经典系列-键值对
  6. 看日记学git摘要~灰常用心的教程
  7. MVC DI
  8. 利用ArrayList对Hashtable其进行排序
  9. LoadRunner结果分析与生成报告
  10. 工控随笔_02_西门子_WinCC的IO域利用C脚本返回值
  11. 记一次Java调优案例分析
  12. 廖雪峰Java6 IO编程-2input和output-7序列化
  13. DDD简明入门之道 - 开篇
  14. redis竞汰数据同步问题解决
  15. Delphi Dll 动态调用例子(3)-仔细看一下
  16. 手淘适配-flexible
  17. 好用的http client库CPP REST SDK
  18. 4.spriing:Bean的生命周期/工厂方法配置Bean/FactoryBean
  19. WPF中的动画——(六)演示图板
  20. Spring MVC前台POST/GET方式传参数的方法

热门文章

  1. Nginx高性能服务器安装、配置、运维 (4) —— Nginx服务、架构及其信号
  2. 关于Modelsim仿真速度的优化
  3. Java动态绑定
  4. 首页的sitecontent地址
  5. c语言学习之基础知识点介绍(十二):结构体的介绍
  6. 再跟SQL谈一谈--基础篇
  7. C#一些小技巧
  8. mysql:1153 Got a packet bigger than ‘max_allowed_packet’ bytes的解决方法
  9. windows server 2003 禁止开机显示“关闭事件跟踪”
  10. Codevs 3729 飞扬的小鸟