CCF-CSP题解 201612-4 压缩编码
2024-09-01 20:34:02
\(CSP\)也考\(DP\)的嘛...想了两小时贪心的我在宿舍凌乱...
还是智障+老花啊...这不是一道区间合并裸题嘛...石子合并啊...
再看看这\(3s\)的时限,\(O(n^3)\)都够了,何必想那么久贪心呢...
#include <bits/stdc++.h>
typedef long long LL;
const int maxn = 1000;
using namespace std;
LL a[maxn + 10];
LL dp[maxn + 10][maxn + 10];
int main()
{
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%lld", a + i);
for (int i = 2; i <= n; i++)
a[i] += a[i - 1];
memset(dp, 0x3f, sizeof(dp));
for (int i = 1; i <= n; i++)
dp[i][i] = 0;
for (int len = 2; len <= n; len++)
{
for (int l = 1; l + len - 1 <= n; l++)
{
int r = l + len - 1;
for (int mid = l; mid <= r - 1; mid++)
{
dp[l][r] = min(dp[l][r], dp[l][mid] + dp[mid + 1][r]);
}
dp[l][r] += a[r] - a[l - 1];
}
}
if (n == 1)
printf("%lld\n", a[1]);
else
printf("%lld\n", dp[1][n]);
return 0;
}
最新文章
- ES性能测试
- python 3.x urllib学习
- 配置 AEM CQ6 (author + publish + apache dispatcher + ubuntu )
- MAC OS下安装Erlang
- Hibernate和JDBC、EJB比较
- 【自用代码】Json转对象
- SQL函数学习(二):DATEADD() 函数
- redis动态配置
- web传输过程中的gzip压缩
- 搭建开发环境2)Debian8 安装jdk 1.8
- 如何用Fiddler手机抓包
- Python之路(第三十三篇) 网络编程:socketserver深度解析
- 大学jsp实验5request,response
- 大规模数据导入和导出(oracle)
- eclipse里面svn比较之前版本的代码
- GTS-800二次开发基本流程总结
- codestyle 设置问题
- 【更新】搭建 Zookeeper-3.4.11 集群
- jvm层面锁优化+一般锁的优化策略
- 安卓Dialog对话框多次显示而闪退的解决办法
热门文章
- SQL Server设计三范式
- 理解Redis单线程运行模式
- 使用 Angular 打造微前端架构的 ToB 企业级应用
- 用PHP实现一个简易版文件上传功能(超详细讲解)
- C语言基础 -- 变量
- 豆瓣 URLError: <;urlopen error [SSL: CERTIFICATE_VERIFY_FAILED] certificate verify failed (_ssl.c:719)>;
- 源码分析— java读写锁ReentrantReadWriteLock
- insertBefore()
- 【数据结构】之链表(C语言描述)
- 这个七夕节,用Python为女友绘制一张爱心照片墙吧!【华为云技术分享】