hdu4570Multi-bit Trie

时间:2022-09-08 18:38:59

链接

13年长沙邀请赛的题,神题意~

题意:摘自http://blog.csdn.net/libin56842/article/details/9703457

这题题意确实有点难懂,起码对于我这个英语渣渣来说是这样,于是去别人的博客看了下题目意思,归纳起来如下:

给出一个长度为n的数列,将其分成若干段,要求hdu4570Multi-bit Trie最小,其中ai是每一段数列的第一项,bi是每一段的长度,l为将数列分成l段。

比如样例:n=7,A={1 2 4 4 5 4 3},将其分成1 2 4| 4 5| 4| 3,则其所用空间为1*2^3+4*2^2+4*2^1+3*2^1=38,而如果分成1 2| 4 4 5| 4 3,则其所用空间为1*2^2+4*2^3+4*2^2=52,比38大。

然后就是简单的dp了,类似之前做过的切段。

 #include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
#include<vector>
#include<cmath>
#include<queue>
#include<set>
using namespace std;
#define N 110
#define LL __int64
#define INF 1e18
const double eps = 1e-;
const double pi = acos(-1.0);
const double inf = ~0u>>;
LL dp[N][N],pp[];
int a[N];
void init()
{
int i;
pp[] = ;
for(i = ;i <= ; i++)
pp[i] = pp[i-]*;
}
int main()
{
int i,j,n,t,g;
cin>>t;
init();
while(t--)
{
scanf("%d",&n);
for(i = ;i <= n; i++)
scanf("%d",&a[i]);
for(i = ;i <= n; i++)
for(j = ;j <= n ;j++)
dp[i][j] = INF;
if(n<=)
dp[][n] = a[]*pp[n];
for(i= ;i <= n; i++)
if(i<=)
dp[][i] = pp[i]*a[];
for(i = ;i <= n; i++)
{
for(j = i ; j <= n; j++)
{
for(g = i-; g < j; g++)
if(j-g>) continue;
else
dp[i][j]= min(dp[i-][g]+pp[j-g]*a[g+],dp[i][j]);
}
}
LL minz = INF;
for(i = ; i <= n; i++)
{
minz = min(minz,dp[i][n]);
// cout<<dp[i][n]<<" "<<i<<endl;
}
cout<<minz<<endl;
}
return ;
}

hdu4570Multi-bit Trie的更多相关文章

  1. 基于trie树做一个ac自动机

    基于trie树做一个ac自动机 #!/usr/bin/python # -*- coding: utf-8 -*- class Node: def __init__(self): self.value ...

  2. 基于trie树的具有联想功能的文本编辑器

    之前的软件设计与开发实践课程中,自己构思的大作业题目.做的具有核心功能,但是还欠缺边边角角的小功能和持久化数据结构,先放出来,有机会一点点改.github:https://github.com/chu ...

  3. &lbrack;LeetCode&rsqb; Implement Trie &lpar;Prefix Tree&rpar; 实现字典树&lpar;前缀树&rpar;

    Implement a trie with insert, search, and startsWith methods. Note:You may assume that all inputs ar ...

  4. hihocoder-1014 Trie树

    hihocoder 1014 : Trie树 link: https://hihocoder.com/problemset/problem/1014 题意: 实现Trie树,实现对单词的快速统计. # ...

  5. 【BZOJ-2938】病毒 Trie图 &plus; 拓扑排序

    2938: [Poi2000]病毒 Time Limit: 1 Sec  Memory Limit: 128 MBSubmit: 609  Solved: 318[Submit][Status][Di ...

  6. Poj The xor-longest Path 经典题 Trie求n个数中任意两个异或最大值

    Time Limit: 2000MS   Memory Limit: 65536K Total Submissions: 5646   Accepted: 1226 Description In an ...

  7. 二分&plus;DP&plus;Trie HDOJ 5715 XOR 游戏

    题目链接 XOR 游戏 Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)Total ...

  8. 【hihoCoder】1036&Tab;Trie图

    题目:http://hihocoder.com/problemset/problem/1036 给一个词典dict,词典中包含了一些单词words.要求判断给定的一个文本串text中是否包含这个字典中 ...

  9. 萌新笔记——C&plus;&plus;里创建 Trie字典树(中文词典)(一)(插入、遍历)

    萌新做词典第一篇,做得不好,还请指正,谢谢大佬! 写了一个词典,用到了Trie字典树. 写这个词典的目的,一个是为了压缩一些数据,另一个是为了尝试搜索提示,就像在谷歌搜索的时候,打出某个关键字,会提示 ...

  10. 洛谷P2412 查单词 &lbrack;trie树 RMQ&rsqb;

    题目背景 滚粗了的HansBug在收拾旧英语书,然而他发现了什么奇妙的东西. 题目描述 udp2.T3如果遇到相同的字符串,输出后面的 蒟蒻HansBug在一本英语书里面找到了一个单词表,包含N个单词 ...

随机推荐

  1. 并查集&lpar;Disjoint Set&rpar;

    在一些有N个元素的集合应用问题中,我们通常是在开始时让每个元素构成一个单元素的集合,然后按一定顺序将属于同一组的元素所在的集合合并,其间要反复查找一个元素在哪个集合中.这一类问题其特点是看似并不复杂, ...

  2. 【简译】Windows 线程基础

    翻译一篇关于windows线程的文章,原文在此.第一次翻译,如有错误请多指教 =========================================华丽的分割线============== ...

  3. Windows Azure 上的 Symfony,适用于 PHP 开发者的强大组合

     发布于 2014-06-13 作者 陈 忠岳 Symfony 是针对 PHP 开发者的流行开源 Web 应用框架.现在,您可以更轻松地在 Windows Azure 上使用它,这都归功于 Ben ...

  4. jquery获取css color 值返回RGB

    css代码如下: a, a:link, a:visited { color:#4188FB; } a:active, a:focus, a:hover { color:#FFCC00; } js代码如 ...

  5. aliyun云服务器硬件性能测试

    1.所购买阿里云服务器信息 2.dd命令测试 3.

  6. 3、File类之创建、删除、重命名、判断方法

    一般我们调用内置类的方法,都是指调用其成员方法,故而以下几种方法都是File类的成员方法,常用的有以下3种, 分别是 //创建 public boolean createNewFile() publi ...

  7. 用DIV&plus;CSS做网页里要设置body和&ast;规定内容

    body{}表示是对body标签的设置,就是<html><head></head><body></body></html> 里面 ...

  8. NOIP2017衢二中旅游记Day 1

    NOIP前一天下午早早的去了衢州: 车程大概在4个半小时左右: 车上大家都一脸颓废,并混杂着动听的音乐: 到了衢州二中,立刻跑去吃晚饭: 吃饭的队伍特别长,吃面的却空无一人: 我毅然决然地选择了去吃面 ...

  9. 【翻译】在Ext JS 6通用应用程序中使用既共享又特定于视图的代码

    原文:Using Both Shared and View-Specific Code in an Ext JS 6 Universal App 在本文,在展示如何编写Ext JS 6通用应用程序代码 ...

  10. LeetCode(101):对称二叉树

    Easy! 题目描述: 给定一个二叉树,检查它是否是镜像对称的. 例如,二叉树 [1,2,2,3,4,4,3] 是对称的. 1 / \ 2 2 / \ / \ 3 4 4 3 但是下面这个 [1,2, ...