【hdu4570】Multi-bit Trie 区间DP

标签：区间dp

hdu4570 http://acm.hdu.edu.cn/showproblem.php?pid=4570

题意：这题题意理解变态的。转自大神博客：

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

给出一个长度为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大。

思路：区间DP

用dp[i][j]表示第 i 层到第 j 层用的最少内存

初始化工作是，根据题目，数据保证答案中的压缩不会超过20层，所以当 j-i 小于20的时候，dp[i][j]初始化为 a[i]* 2&(j-i+1)，否则初始化为一个INF

方程 dp[i][j]= min(dp[i][j], dp[i][k]+dp[k+1][j] ) i<=k<j

自WA点：构造解时候，i 和 j都该逆序遍历

 #include <iostream>

 #define N 65

 using namespace std;

 const long long INF = 1LL<<;

 long long dp[N][N],a[N];

 int main()

 {

     int _;

     cin>>_;

     while(_--)

     {

         int n,i,j,k;

         cin>>n;

         for(i=;i<n;i++)    cin>>a[i];

         for(i=;i<n;i++)

             for(j=i;j<n;j++)

                 if(j-i<)  dp[i][j]=a[i]*(<<(j-i+));

                 else        dp[i][j]=INF;

         for(i=n-;i>=;i--)

             for(j=n-;j>=i;j--)

                 for(k=i;k<j;k++)

                     dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+][j]);

         cout<<dp[][n-]<<endl;

     }

     return ;

 }

巴特西

【hdu4570】Multi-bit Trie 区间DP

最新文章

热门文章