算法提高课 第一章 动态规划 区间DP
282. 石子合并
#include
#include
#include
using namespace std;
const int N = 305,INF = 0x3f3f3f3f;
int f[N][N],a[N],s[N];
int n;
int main()
{
cin>>n;
for(int i = 1;i <= n;i++)
{
cin>>a[i];
s[i] = s[i-1] + a[i];
}
for(int len = 2;len <= n;len++) //区间长度为1时，不需要合并，代价为0，故长度从2开始枚举
{
for(int i = 1;i + len - 1 <= n;i++)
{
int l = i, r = i + len - 1;//左右边界
f[l][r] = INF;
for(int k = l;k < r;k++) //分界点 [l,r-1]
{
f[l][r] = min(f[l][r],f[l][k] + f[k+1][r] + s[r] - s[l-1]);
}
}
}
cout< 1068. 环形石子合并
#include
#include
#include
using namespace std;
const int N = 410,INF = 0x3f3f3f3f;
int a[N],n;
int f[N][N];//f[l][r]:考虑长度不超过n的区间[l,r]中两两合并的所有方案中，得分总和最大值
int g[N][N];//f[l][r]:考虑长度不超过n的区间[l,r]中两两合并的所有方案中，得分总和最小值
int s[N];//前缀和
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i ++ )
{
scanf("%d", &a[i]);
a[i+n] = a[i];
}
for (int i = 1; i <= 2*n; i ++ )
{
s[i] = s[i-1] + a[i];
}
memset(f,-INF,sizeof f);
memset(g,INF,sizeof g);
for(int len = 1;len<=n;len++) //枚举区间长度
{
for(int i = 1;i+len-1<=2*n;i++)//枚举区间起点
{
int l = i,r = i+len-1;//算出左右端点
if(len == 1)//注意：若长度为1，无需合并，特殊处理
{
f[l][r] = g[l][r] = 0;
continue;
}
for(int k = l;k 320. 能量项链
直接当成珠子来看待即可，模拟合并过程。
区间长度为n
#include
#include
#include
using namespace std;
const int N = 210;
int a[N],n;
int f[N][N];//f[l][r]:区间[l,r]的所有合并方案中，能量的最大值
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i ++ )
{
scanf("%d", &a[i]);
a[i+n] = a[i];
}
memset(f,-0x3f,sizeof f);
for(int len = 1;len<=n;len++)
{
for(int l = 1;l+len-1<=2*n;l++)
{
int r = l+len-1;
if(len == 1)//长度为1，无需合并
{
f[l][r] = 0;
continue;
}
for(int k = l;k 4 5 7 4
//这里的过程同石子合并，这里不难想到若将l到k的珠子合并之后会变成一个首是l而尾k+1的珠子；
//同理若将k+1到r的珠子合并之后会变成一个首是k+1而尾r+1的珠子；
}
}
}
int ans = -1;
for (int i = 1; i <= n; i ++ )
{
ans = max(ans,f[i][i+n-1]);
}
cout< 1069. 凸多边形的划分
区间DP+高精度
#include
#include
#include
#include
using namespace std;
typedef long long LL;
const int N = 55;
int a[N],n;
vector f[N][N];
vectoradd(vector&a,vector&b) //高精度加法
{
vectorc;
LL t = 0;
for(int i = 0;i&a,vector&b) //高精度比大小
{
if(a.size()!=b.size()) return a.size() > b.size();
for(int i = a.size()-1;i>=0;i--)
{
if(a[i] > b[i]) return 1;
if(a[i] < b[i]) return -1;
}
return 0;
}
vectormul(vector&a,LL b) //高精度乘法
{
vectorc;
LL t = 0;
for(int i = 0;i&a) //输出，注意略去前导0
{
int i = a.size() - 1;
while(i>=0 && a[i] == 0) --i;
while(i>=0)
{
cout<{0};
continue;
}
f[l][r] = vector(N,9); //初始化为正无穷
for(int k = l+1;kt;
t.push_back(a[l]);
t = mul(t,a[k]);
t = mul(t,a[r]);
t = add(t,f[l][k]);
t = add(t,f[k][r]);
if(cmp(f[l][r],t)>0) f[l][r] = t;
//f[l][r] = min(f[l][r],f[l][k] + f[k][r] + a[l]*a[k]*a[r]);
}
}
}
print(f[1][n]);
return 0;
}
479. 加分二叉树
用root[L,R]记录划分方案(根结点)
#include
#include
#include
using namespace std;
const int N = 35;
int a[N],n;
int f[N][N];
int root[N][N];
void dfs(int l,int r) //前序遍历
{
if(l>r) return;
int t = root[l][r];
cout< f[l][r]) //题目要求字典序最小，因此大于再更新
{
f[l][r] = score;
root[l][r] = k;
}
//f[l][r] = max(f[l][r],f[l][k]*f[k+1][r] + a[k]);
}
}
}
cout< 321. 棋盘分割
#include
#include
#include
#include
using namespace std;
const int N = 10,K = 16,INF = 0x3f3f3f3f;
double f[N][N][N][N][K];//f[x1][y1][x2][y2][k]:(x1,y1)到(x2,y2)区域分成k块的所有方案中，方差和最小的
int s[N][N];//二维前缀和
int n;
double X;
double get(int x1,int y1,int x2,int y2) //计算出(x1,y1)到(x2,y2)区域得分的方差，前缀和O(1)算区域和
{
double sum = s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1];
sum -= X;
return 1.0*sum * sum;
}
double dp(int x1,int y1,int x2,int y2,int k)
{
double &v = f[x1][y1][x2][y2][k];
if(v>=0) return v;//记忆化搜索
if(k == n) return v = get(x1,y1,x2,y2);//注意：分为n块时，仍需要算出矩形区域内的方差
double res = INF;
for(int t = x1;t