网站租用价格,商城网站建设都有哪些类型,wordpress后台菜单修改,互联网医疗题目描述 小A想把他满屋子的书整理一下。书本分成若干堆。每一堆的书本都有质量w和价值v。小A的任务是将所有书合成一堆。因为小A认为合并i#xff0c;j两堆的书所需要的力为w[i]-v[i]w[j]-v[j]。合并后的书堆的质量和价值均为合并前两堆书的质量和价值的总和。也就是说#…题目描述 小A想把他满屋子的书整理一下。书本分成若干堆。每一堆的书本都有质量w和价值v。小A的任务是将所有书合成一堆。因为小A认为合并ij两堆的书所需要的力为w[i]-v[i]w[j]-v[j]。合并后的书堆的质量和价值均为合并前两堆书的质量和价值的总和。也就是说合并ij两堆的书后ww[i]w[j]vv[i]v[j]。合并只能在相邻两堆书本间进行。书本合并前后位置不变。如果将123中的12进行合并那么合并结果为33再将33合并为61236指质量。请你帮他计算最少需要花费多少力气。 输入格式 第一行是一个整数n2≤n≤400 第二行至第n1行每行两个整数w和v0VW≤1000。 输出格式 仅一行只有一个整数表示花费的最少力气。 输入样例 3 6 5 9 7 11 2 输出样例 15 题解 区间dp水题。因为只能合并相邻两堆所以直接套模板就行了。 #include iostream
#include algorithm
#include cstdio
#include cmath
#define MAXN 401using namespace std;int n;
int w[MAXN], v[MAXN];
int f[MAXN][MAXN];
int sw[MAXN][MAXN], sv[MAXN][MAXN];int main()
{cin n;for(register int i 1; i n; i){cin w[i] v[i];sw[i][i] w[i];sv[i][i] v[i];}for(register int i 1; i n; i){for(register int j i 1; j n; j){sw[i][j] sw[i][j - 1] w[j];sv[i][j] sv[i][j - 1] v[j];}}for(register int i n - 1; i 1; i--){for(register int j i 1, m 1000000000; j n; j, m 1000000000){for(register int k i; k j; k){m min(m, f[i][k] f[k 1][j] sw[i][j] - sv[i][j]);}f[i][j] m;}}cout f[1][n];return 0;
} 参考程序 转载于:https://www.cnblogs.com/kcn999/p/10805043.html
