企业网站开发使用方法,昆山移动网站建设,公司网站建设技术的发展,wordpress google字体 插件一、石子合并 (经典例题)
设有 N 堆石子排成一排#xff0c;其编号为 1,2,3,…,N。 每堆石子有一定的质量#xff0c;可以用一个整数来描述#xff0c;现在要将这 N 堆石子合并成为一堆。 每次只能合并相邻的两堆#xff0c;合并的代价为这两堆石子的质量之和#xff0c;…一、石子合并 (经典例题)
设有 N 堆石子排成一排其编号为 1,2,3,…,N。 每堆石子有一定的质量可以用一个整数来描述现在要将这 N 堆石子合并成为一堆。 每次只能合并相邻的两堆合并的代价为这两堆石子的质量之和合并后与这两堆石子相邻的石子将和新堆相邻合并时由于选择的顺序不同合并的总代价也不相同。 例如有 4 堆石子分别为 1 3 5 2 我们可以先合并 1、2 堆代价为 4得到 4 5 2 又合并 1、2 堆代价为 9得到 9 2 再合并得到 11总代价为 491124 如果第二步是先合并 2、3 堆则代价为 7得到 4 7最后一次合并代价为 11总代价为 471122。
问题是找出一种合理的方法使总的代价最小输出最小代价。
输入 第一行一个数 N 表示石子的堆数 N (1 ≤ N ≤ 300)。 第二行 N 个数表示每堆石子的质量(均不超过 1000)。
输出 输出一个整数表示最小代价。
Input 4 1 3 5 2
Output 22解析 用一个状态表示一个区间f[i][j] 表示将第 i 堆石子到第 j 堆石子合并成一堆石子的合并方式的集合。 状态转移 例如将 区间 [i,j] 分为 [i,k] 和 [k1,j] 枚举 k 在区间[i,j]的位置就能找到最小代价使得 合并这两个区间的代价最小即 f[i][k]f[k1,j] 的值最小再加上一个第 i 堆到第 j 堆的总重量即可。 因为在计算状态的时候得保证在这个状态之前的状态已经计算完毕所以可以采用循环区间长度从小到大的方式进行计算。
#include bits/stdc.h
using namespace std;
#define int long long
#define endl \n
#define ios ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
int gcd(int a,int b) { return b? gcd(b,a%b) : a; }
typedef pairint,int PII;
const double PIacos(-1.0);
const int N310;
int n;
int s[N];
int f[N][N];
void solve()
{cinn;for (int i1;in;i) cins[i];for (int i1;in;i) s[i] s[i-1];for (int len1;lenn;len)for (int i1;ilen-1n;i){int li,rilen-1;if(len!1) f[l][r]2e9; //因为当len1时只有一堆石子不需要合并代价为0for (int kl;kr;k)f[l][r]min(f[l][r],f[l][k]f[k1][r]s[r]-s[l-1]);}coutf[1][n];
}
signed main()
{ios;int T1;//cinT;while (T--) solve();return 0;
} 二、 环形石子合并 (加个环)
将 n 堆石子绕圆形操场排放现要将石子有序地合并成一堆。 规定每次只能选相邻的两堆合并成新的一堆并将新的一堆的石子数记做该次合并的得分。 请编写一个程序读入堆数 n 及每堆的石子数并进行如下计算 选择一种合并石子的方案使得做 n−1 次合并得分总和最大。 选择一种合并石子的方案使得做 n−1 次合并得分总和最小。
输入 第一行包含整数 n (1 ≤ n ≤ 200)表示共有 n 堆石子。 第二行包含 n 个整数分别表示每堆石子的数量。
输出 共两行第一行为合并得分总和最小值第二行为合并得分总和最大值。
Input 4 4 5 9 4
Output 43 54
解析 与上一题的石子合并的想法基本相似不同的是这道题的石堆的摆放方式是环式的。 在上道题的基础上将这个环断开变成一条链枚举每个断点。 不过直接枚举的话时间复杂度是 n^4超时了。 我们可以将数组读入再将数组复制一遍再接到这个数组上。 这样时间复杂度就降下来了时间复杂度在 n^3。 注意在做这种环式的题就可以多想一想这样的方法
#include bits/stdc.h
using namespace std;
#define int long long
#define endl \n
#define ios ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
int gcd(int a,int b) { return b? gcd(b,a%b) : a; }
typedef pairint,int PII;
const double PIacos(-1.0);
const int N410;
int n;
int a[N],s[N];
int f[N][N],g[N][N];
void solve()
{cinn;for (int i1;in;i) cina[i],a[in]a[i];for (int i1;i2*n;i) s[i]s[i-1]a[i];for (int len1;lenn;len) //一层循环枚举区间长度for (int i1;ilen-12*n;i) //二层循环枚举区间的左右端点{int li,rilen-1;if (len!1) f[l][r]2e9,g[l][r]-2e9;for (int kl;kr;k) //状态转移{f[l][r]min(f[l][r],f[l][k]f[k1][r]s[r]-s[l-1]);g[l][r]max(g[l][r],g[l][k]g[k1][r]s[r]-s[l-1]);}}int minx2e9,maxx-2e9; //找到最小值最大值for (int i1;in;i) {minxmin(minx,f[i][in-1]);maxxmax(maxx,g[i][in-1]);}coutminxendlmaxxendl;
}
signed main()
{ios;int T1;//cinT;while (T--) solve();return 0;
}
三、能量项链 (跟上个题一样)
在 Mars 星球上每个 Mars 人都随身佩带着一串能量项链在项链上有 N 颗能量珠。 能量珠是一颗有头标记与尾标记的珠子这些标记对应着某个正整数。 并且对于相邻的两颗珠子前一颗珠子的尾标记一定等于后一颗珠子的头标记。 因为只有这样通过吸盘吸盘是 Mars 人吸收能量的一种器官的作用这两颗珠子才能聚合成一颗珠子同时释放出可以被吸盘吸收的能量。
如果前一颗能量珠的头标记为 m尾标记为 r后一颗能量珠的头标记为 r尾标记为 n则聚合后释放的能量为 m×r×nMars 单位新产生的珠子的头标记为 m尾标记为 n。 需要时Mars 人就用吸盘夹住相邻的两颗珠子通过聚合得到能量直到项链上只剩下一颗珠子为止。 显然不同的聚合顺序得到的总能量是不同的请你设计一个聚合顺序使一串项链释放出的总能量最大。
例如设 N44 颗珠子的头标记与尾标记依次为 (23)(35)(510)(102)。 我们用记号 ⊕ 表示两颗珠子的聚合操作(j⊕k) 表示第 jk 两颗珠子聚合后所释放的能量。则 第 4、1 两颗珠子聚合后释放的能量为(4⊕1)10×2×360。 这一串项链可以得到最优值的一个聚合顺序所释放的总能量为 ((4⊕1)⊕2)⊕3)10×2×310×3×510×5×10710。
输入 输入的第一行是一个正整数 N (4 ≤ N ≤ 100)表示项链上珠子的个数。 第二行是 N 个用空格隔开的正整数所有的数均不超过 1000第 i 个数为第 i 颗珠子的头标记当 iN 时第 i 颗珠子的尾标记应该等于第 i1 颗珠子的头标记第 N 颗珠子的尾标记应该等于第 1 颗珠子的头标记。 至于珠子的顺序你可以这样确定将项链放到桌面上不要出现交叉随意指定第一颗珠子然后按顺时针方向确定其他珠子的顺序。
输出 输出只有一行是一个正整数 E (1 ≤ E ≤ 2e9)为一个最优聚合顺序所释放的总能量。
Input 4 2 3 5 10
Output 710
解析 跟上一题一样纯套路。
//代码一:开个结构体存储头和尾相当于一个点就跟上道题一模一样了
#include bits/stdc.h
using namespace std;
#define int long long
#define endl \n
#define ios ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
int gcd(int a,int b) { return b? gcd(b,a%b) : a; }
typedef pairint,int PII;
const double PIacos(-1.0);
const int N400;
struct node
{int x,y;
}str[N];
int n;
int a[N];
int f[N][N];
void solve()
{cinn;for (int i1;in;i) cina[i];for (int i1;in;i){if (i1) str[i]{a[n],a[i]};else str[i]{a[i-1],a[i]};str[in]str[i];}for (int len1;lenn;len)for (int i1;ilen-12*n;i){int li,rilen-1;if (len!1) f[l][r]-2e9;for (int kl;kr;k){f[l][r]max(f[l][r],f[l][k]f[k1][r]str[l].x*str[k].y*str[r].y); //左区间左端点的头*左区间右端点的尾*右区间右端点的尾}}int ans-2e9;for (int i1;in;i) ansmax(ans,f[i][in-1]);coutans;
}
signed main()
{ios;int T1;//cinT; while (T--) solve();return 0;
}//代码二
//划分方式:f(l,r)f(l,k)f(k,r)a[l]*a[k]*a[r]
#include bits/stdc.h
using namespace std;
#define int long long
#define endl \n
#define ios ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
int gcd(int a,int b) { return b? gcd(b,a%b) : a; }
typedef pairint,int PII;
const double PIacos(-1.0);
const int N400;
int n;
int a[N];
int f[N][N];
void solve()
{cinn;for (int i1;in;i) cina[i],a[in]a[i];for (int len3;lenn1;len) //至少 3 个点for (int i1;ilen-12*n;i){int li,rilen-1;f[l][r]-2e9;for (int kl;kr;k){f[l][r]max(f[l][r],f[l][k]f[k][r]a[l]*a[k]*a[r]); }}int ans-2e9;for (int i1;in;i) ansmax(ans,f[i][in]); //查找区间长度为 n1 的coutans;
}
signed main()
{ios;int T1;//cinT; while (T--) solve();return 0;
} 四、凸多边形的划分
给定一个具有 N 个顶点的凸多边形将顶点从 1 至 N 标号每个顶点的权值都是一个正整数。 将这个凸多边形划分成 N−2 个互不相交的三角形对于每个三角形其三个顶点的权值相乘都可得到一个权值乘积试求所有三角形的顶点权值乘积之和至少为多少。
输入 第一行包含整数 N (N ≤ 50)表示顶点数量。 第二行包含 N 个整数依次为顶点 1 至顶点 N 的权值。
输出 输出仅一行为所有三角形的顶点权值乘积之和的最小值。 数据保证所有顶点的权值都小于 1e9
Input 5 121 122 123 245 231
Output 12214884 解析 f[l][r] 表示 所有 由(l,l1)(l1,l2)……(r-1,r)(r,l)这些边组成的多边形 划分成三角形的方案的集合。 跟上道题的划分是一样的不过不需要破环成链因为枚举哪一条边都是一样的。 这里的运算数据太大需要高精度运算。
//代码一:没有加高精度的代码
#include bits/stdc.h
using namespace std;
#define int long long
#define endl \n
#define ios ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
int gcd(int a,int b) { return b? gcd(b,a%b) : a; }
typedef pairint,int PII;
const double PIacos(-1.0);
const int N110;
int n;
int w[N];
int f[N][N];
int INF1e18;
void solve()
{cinn;for (int i1;in;i) cinw[i];for (int len3;lenn;len)for (int i1;ilen-1n;i){int li,rilen-1;f[l][r]INF;for (int kl;kr;k){f[l][r]min(f[l][r],f[l][k]f[k][r]w[l]*w[k]*w[r]);}}coutf[1][n];
}
signed main()
{ios;int T1;//cinT; while (T--) solve();return 0;
}//代码二:加了高精度的代码
#include bits/stdc.h
using namespace std;
#define int long long
#define endl \n
#define ios ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
int gcd(int a,int b) { return b? gcd(b,a%b) : a; }
typedef pairint,int PII;
const double PIacos(-1.0);
const int N55,M35,INF1e9;
int n;
int w[N];
int f[N][N][M];
int c[M];
void add(int a[],int b[])
{memset(c,0,sizeof c);int t0;for (int i0;iM;i){t a[i]b[i];c[i]t%10;t /10;}memcpy(a,c,sizeof c);
}
void mul(int a[],int b)
{memset(c,0,sizeof c);int t0;for (int i0;iM;i){t a[i]*b;c[i]t%10;t /10;}memcpy(a,c,sizeof c);
}
int cmp(int a[],int b[])
{for (int iM-1;i0;i--){if (a[i]b[i]) return 1;else if (a[i]b[i]) return -1;}return 0;
}
void print(int a[])
{int kM-1;while (k!a[k]) k--;while (k0) couta[k--];coutendl;
}
int temp[M];
void solve()
{cinn;for (int i1;in;i) cinw[i];for (int len3;lenn;len)for (int i1;ilen-1n;i){int li,rilen-1;f[l][r][M-1]1;for (int kl1;kr;k){memset(temp,0,sizeof temp);temp[0]w[l];mul(temp,w[k]);mul(temp,w[r]);add(temp,f[l][k]);add(temp,f[k][r]);if (cmp(f[l][r],temp)0) memcpy(f[l][r],temp,sizeof temp);}}print(f[1][n]);
}
signed main()
{ios;int T1;//cinT; while (T--) solve();return 0;
}
