首页 > 代码库 > hdu 4570 Multi-bit Trie(dp)

hdu 4570 Multi-bit Trie(dp)

2024-09-05 06:11:15   237人阅读

题目链接:hdu 4570 Multi-bit Trie

题意：

这题的题意要看半天，其实就是让你求∑ai*(2^bi)，一个长度为n的数列，将其分成若干段（每一段的长度要<=20）， 要求∑ai*(2^bi)最小，其中ai是每一段数列的第一项，bi是每一段的长度。

比如样例：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。

题解：

考虑dp[i]表示前i个分好后的最优解，则有dp[i]=min(dp[i]，dp[j-1]+a[j]*(1<<(i-j+1))),其中i-j+1<=20。

技术分享 
 1 #include<bits/stdc++.h>
 2 #define mst(a,b) memset(a,b,sizeof(a))
 3 #define F(i,a,b) for(int i=a;i<=b;++i)
 4 using namespace std;
 5 typedef long long ll;
 6 
 7 int t,n;
 8 ll sum[70],a[70],dp[70];
 9 
10 int main(){
11     scanf("%d",&t);
12     while(t--)
13     {
14         scanf("%d",&n);
15         F(i,1,n)scanf("%lld",a+i),sum[i]=sum[i-1]+a[i];
16         F(i,1,n)
17         {
18             dp[i]=dp[i-1]+a[i]*2;
19             F(j,1,i-1)if(i-j+1<=20)
20             dp[i]=min(dp[i],dp[j-1]+a[j]*(1ll<<(i-j+1)));
21         }
22         printf("%lld\n",dp[n]);
23     }
24     return 0;
25 }
View Code

 

hdu 4570 Multi-bit Trie(dp)


联系
我们