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;
}