hdu-4570-Multi-bit Trie-简单区间DP

本文主要是介绍hdu-4570-Multi-bit Trie-简单区间DP，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

有的时候，你看不懂题，你就A不了题（这不是废话么。。。）

这个题实在是太恶心了，做法很简单，题意很难懂！！

题意：

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

给出一个长度为n的数列，将其分成若干段，要求最小，其中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大。

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <ctype.h>
#include <queue>
#include <map>
#include <algorithm>
using namespace std;
#define maxn 110
#define LL __int64
LL mp[maxn][maxn];
LL a[maxn];
LL dos(LL x,LL y)
{if(mp[x][y])return mp[x][y];LL minn=a[x];for(LL i=x;i<=y;i++)minn=minn*2;if(y-x+1>20){minn=0;for(LL i=x;i<=y;i++)minn+=a[i]*2;}for(LL i=x;i<y;i++){minn=min(minn,dos(x,i)+dos(i+1,y));}mp[x][y]=minn;return minn;
}
int main()
{int T,n;scanf("%d",&T);while(T--){memset(mp,0,sizeof(mp));scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&a[i]);}printf("%I64d\n",dos(1,n));}return 0;
}

这篇关于hdu-4570-Multi-bit Trie-简单区间DP的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---