2019河北省大学生程序设计竞赛（重现赛）- C 分治

题目链接：https://ac.nowcoder.com/acm/contest/903/C 题目大意： 思路：直接枚举攻打点，分成两个区间，进行分治就行了。记忆化递归。

#include<bits/stdc++.h> #define LL long long using namespace std; const int maxn=2e5+10; LL a[105]; LL dp[105][105]; LL dfs(int L, int R) { if(dp[L][R]!=-1) { return dp[L][R]; } if(R<=L) { return 0; } LL ans=((LL)1<<63)-1; for(int i=L;i<=R;i++)//枚举攻打点 { ans=min(ans, dfs(L, i-1)+dfs(i+1, R)+(R-L)*a[i]);//分治 } return dp[L][R]=ans; } int main() { int t; scanf("%d",&t); while(t--) { int n; memset(dp, -1, sizeof(dp)); scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); } printf("%lld\n",dfs(1, n)); } return 0; }