题目意思：
转化题意，就是给n个数，求一个划分使得每一段的第一个数乘以2的该段个数次方的和最小。每一段的个数不超过20。
解题思路：
dp[i]表示i个数时满足题目要求的划分的最小总和。
dp[i]=Min(dp[i],sa[i-j+1]*bi[j]+dp[i-j]);
代码：
#include #include #include #include #include #include #include #include #include #include #include #include #include #define eps 1e-6 #define INF 0x1f1f1f1f #define PI acos(-1.0) #define ll __int64 #define lson l,m,(rt<<1) #define rson m+1,r,(rt<<1)|1 //#pragma comment(linker, "/STACK:1024000000,1024000000") using namespace std; /* freopen("data.in","r",stdin); freopen("data.out","w",stdout); */ #define Maxn 70 ll dp[Maxn],sa[Maxn]; int n; int bi[25]; ll Min(ll a,ll b) { return a=j;j++) //不超过20个， { dp[i]=Min(dp[i],sa[i-j+1]*bi[j]+dp[i-j]); } } printf("%I64d\n",dp[n]); } return 0; }