计算概论A代码总结Ⅲ（动态规划类）-创新互联
动态规划大体可分为：序列类、区间DP、背包类问题等几类，主要是需要找到不同维数组所代表的实际含义（状态）、确定状态转移方程、并且设置初始边界条件，使循环得以进行
一、序列类
1.大上升子序列（拦截导弹、合唱队型、药剂稀释）
//大上升子序列√
#include#include#include
using namespace std;
const int maxn = 100;
int dp[maxn];
int a[maxn];
int main() {
int n;
cin >>n;
for (int i = 0; i< n; i++) {
cin >>a[i];
}
dp[0] = 1;
for (int i = 1; i< n; i++) {
dp[i] = 1;
for (int j = i - 1; j >= 0; j--) {
if (a[i] >a[j]) {
dp[i] = max(dp[i], dp[j] + 1);
}
}
}
int ans = dp[0];
for (int i = 1; i< n; i++) {
ans = max(ans, dp[i]);
}
cout<< ans<< endl; return 0;
//} 2.大子序列和
大子序列和
#include#include#include
const int maxn = 100;
using namespace std;
int main() {
int dp[maxn];
int a[maxn];
int n;
cin >>n;
for (int i = 0; i< n; i++) {
cin >>a[i];
}
dp[0] = a[0];
for (int i = 1; i< n; i++) {
dp[i] = max(dp[i - 1] + a[i], a[i]);
}
int maxsum = -10;
for (int i = 0; i< n; i++) {
maxsum = max(maxsum, dp[i]);
}
cout<< maxsum<< endl; return 0;
} 3.双侧大子序列和（poj）
//双侧大子段和
#include#include
#includeusing namespace std;
const int maxn = 99999;
const int minn = -99999;
int left_sum[maxn];
int right_sum[maxn];
int a[maxn];
void init(int n) {
for (int i = 0; i< n; i++) {
left_sum[i] = minn;
right_sum[i] = minn;
}
}
int main() {
int m;
cin >>m;
while (m--) {
int n;
cin >>n;
for (int i = 0; i< n; i++) {
cin >>a[i];
}
init(n);
left_sum[0] = a[0];
for (int i = 1; i< n; i++) {
left_sum[i] = max(left_sum[i - 1] + a[i], a[i]);
}
int temp = minn;
for (int i = 0; i< n; i++) {
temp = temp >left_sum[i] ? temp : left_sum[i];
left_sum[i] = temp;
}
right_sum[n - 1] = a[n - 1];
for (int i = n - 2; i >= 0; i--) {
right_sum[i] = max(right_sum[i + 1] + a[i], a[i]);
}
temp = minn;
for (int i = n - 1; i >= 0; i--) {
temp = temp >right_sum[i] ? temp : right_sum[i];
right_sum[i] = temp;
}
int ans =minn;
for (int k = 0; k< n - 1; k++) {
int v = left_sum[k] + right_sum[k + 1];
ans = max(ans, v);
}
cout<< ans<< endl;
}
} 二、背包类问题
1.0-1背包问题
0-1背包问题
#include#include#include
#include#includeusing namespace std;
const int maxn = 100;
int main() {
int dp[maxn][maxn];
memset(dp, 0, sizeof(dp));
int N, W;
cin >>N >>W;
int w[maxn]; int v[maxn];
for (int i = 1; i<= N; i++) {
cin >>w[i] >>v[i];
}
for (int i = 1; i<= N; i++) {//一定要注意这里的标号，背包问题从1开始方便计算不同的物品编号
for (int j = w[i]; j<= W; j++) {//for循环的终止条件
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);
}
}
cout<< dp[N][W];
return 0;
} 2.完全背包问题
//完全背包问题
#include#include#include
#include#includeusing namespace std;
const int maxn = 100;
int main() {
int dp[maxn][maxn];
memset(dp, 0, sizeof(dp));
int n, w;
cin >>n >>w;
int w[maxn]; int v[maxn];
for (int i = 1; i<= n; i++) {
cin >>w[i] >>v[i];
}
for (int i = 1; i<= n; i++) {//一定要注意这里的标号，背包问题从1开始方便计算不同的物品编号
for (int k = 0; k*w[i]<= w; k++) {
for (int j = k*w[i]; j<= w; j++) {//for循环的终止条件
dp[i][j] = max(dp[i][j], dp[i - 1][j - k*w[i]] + k*v[i]);
}
}
}
cout<< dp[n][w];//怎么输出k，把上面那个改一下就好，不用max函数，而用手动的判断
return 0;
}
//如果是多重背包，则改为设置k上限为对应的 3.最佳凑单
//最佳凑单：
#include#include
#includeusing namespace std;
const int maxn = 100;
int main() {
int n, v;
cin >>n >>v;
int a[maxn];
int dp[maxn][maxn];
int sum = 0;
for (int i = 1; i<= n; i++) {
cin >>a[i]; sum += a[i];
}
memset(dp, 0, sizeof(dp));
dp[0][0] = 1;
for (int i = 1; i<= n; i++) {
for (int j = 0; j<= sum; j++) {
if (j >= a[i]) {
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - a[i]]);
}
else {
dp[i][j] = max(dp[i - 1][j], dp[i][j]);
}
}
}
int now = 0;
for (now = v; now<= sum; now++) {
if (dp[n][now])break;
}
if (now >sum)cout<< "null";
else {
cout<< now;
}return 0;
}
//还可以与背包问题结合，假设有每件有限定额，那么一共有多少种凑法(相当于把输出展开即可） 4.天平问题
//天平问题
#include#include#includeusing namespace std;
int main() {
int c, g;
cin >>c >>g;
int len[21];//力臂长度
int wei[21];
int dp[21][15001];
for (int i = 1; i<= c; i++) {
scanf_s("%d", &len[i]);
}
for (int i = 1; i<= g; i++) {
scanf_s("%d", &wei[i]);
}
memset(dp, 0, sizeof(dp));
dp[0][7500] = 1;
for (int i = 1; i<= g; i++) {
for (int j = 0; j<= 15000; j++) {
if (dp[i-1][j]) {
for (int k = 1; k<= c; k++) {
dp[i][j + wei[i] * len[k]] += dp[i - 1][j];
}
}
}
}
cout<< dp[g][7500];
return 0;
} 5.装载问题
//装载问题
#include#include#include
#includeconst int maxn = 100;
using namespace std;
int dp[1000][1000];
int a[maxn];
int main() {
int n;
cin >>n;
int sum = 0;
for (int i = 1; i<= n; i++) {
cin >>a[i]; sum += a[i];
}
int c1, c2;
cin >>c1 >>c2;
memset(dp, 0, sizeof(dp));
dp[0][0] = 1;
for (int i = 1; i<= n; i++) {
for (int j = 0; j<= c1 + c2; j++) {
if (j >= a[i]) {
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - a[i]]);
}
else {
dp[i][j] = max(dp[i][j], dp[i - 1][j]);
}
}
}
int ans1=0;
for ( ans1 = c1; ans1 >= 0; ans1--) {
if (dp[n][ans1])break;
}
int ans[10]; int num = 0;
if (sum - ans1 >c2) { cout<< "can't find a way to Loading"<< endl; return 0; }//提前写好终止条件
for (int i = n; i >= 1; i--) {//初始的dp[n][ans1]肯定是true
if (ans1 - a[i] >= 0 && dp[i - 1][ans1 - a[i]] == true) {
ans[num++] = a[i]; ans1 -= a[i]; a[i] = 0;//先减去再归为0
}//把前面的存起来，把后面的正常输出
}
cout<< "ok,can load it"<< endl;
cout<< "a way is:"<< endl;
cout<< "the first trip load:";
for (int i = num - 1; i >= 0; i--) {
cout<< ans[i]<<' ';
}
cout<< endl;
cout<< "the second trip load:";
for (int i = 1; i<= n; i++) {
if (a[i])cout<< a[i]<< ' ';
}
return 0;
} 6.贪心盗宝问题（阿里巴巴与四十大盗—）
体会与正宗盗宝问题的区别
//贪心盗宝（非正规盗宝法
#includeusing namespace std;
struct treasure {
int w;//weight
int v;//value
int n;//bianhoa
};
treasure t[1000];
bool ok[1000];
int main() {
int m; int n;
cin >>m>>n;
for (int i = 0; i< n; i++) {
cin >>t[i].w >>t[i].v >>t[i].n;
}
//按照value 排序
int tempv = 0; int tempn = 0; int tempw = 0;
for (int i = 0; i< n; i++) {
for (int j = 0; j< n - i; j++) {
if (t[j + 1].v >t[j].v) {
tempw = t[j + 1].w;
t[j + 1].w = t[j].w;
t[j].w = tempw;
tempv = t[j + 1].v;
t[j + 1].v = t[j].v;
t[j].v = tempv;
tempn = t[j + 1].n;
t[j + 1].n = t[j].n;
t[j].n = tempn;
}
}
}//实现降序排列
memset(ok, 0, sizeof(ok));
int ans = 0;
for (int i = 0; i< n; i++) {
if (m >= t[i].w && !ok[t[i].n]) {
ans += t[i].v;
m -= t[i].w;
ok[t[i].n] = 1;
}
}
cout<< ans;
return 0;
} 6.1盗宝问题
盗宝
先写个0-1背包
#include//这和0-1背包不完全一样，0-1背包的横坐标存的是横坐标，还是有这个问题，下标可能会超啊
#include
#include#includeconst int maxn = 1000;
int value[maxn][maxn];
int dp[maxn][maxn];
int weight[maxn][maxn];//第i个洞，第几个作品
int cave[maxn];
using namespace std;
int main() {
int m = 0; int n = 0;
cin >>m >>n;
memset(cave, 0, sizeof(cave));
int max_cave = 0;
for (int i = 1; i<= n; i++) {
int a, b, c;
max_cave = max(max_cave, c);
cin >>a >>b >>c;
value[c][cave[c]] = b;
weight[c][cave[c]] = a;
cave[c]++;
}
//init：初始化
for (int i = 1; i<= max_cave; i++) {
for (int j = 0; j< cave[i]; j++) {
for (int k = weight[i][j]; k<= m; k++) {
dp[i][k] = max(value[i][j], dp[i][k]);
}//承重为大于k时，能获得的大收益，这个这个宝物对应的价值
}
}
//dp
for (int k = 0; k<= m; k++) {
for (int i = 1; i<= max_cave; i++) {
for (int j = 0; j< cave[i]; j++) {
if (k >= weight[i][j]) {
//洞内物品的更新
dp[i][k] = max(dp[i][k], dp[i - 1][k - weight[i][j]] + value[i][j]);
//正常的背包问题，不拿和拿
dp[i][k] = max(dp[i - 1][k], dp[i][k]);
}
else {
dp[i][k] = max(dp[i - 1][k], dp[i][k]);
}
}
}
}
cout<< dp[max_cave][m]<< endl;
return 0;
} 7.human genes
//human genes
#include#include
#include#include#include#include#include#define N 1000
using namespace std;
int s[5][5] = {
{5,-1,-2,-1,-3},
{-1,5,-3,-2,-4},
{-2,-3,5,-2,-2},
{-1,-2,-2,5,-1},
{-3,-4,-2,-1,-1000}
};
int getint(char c) {
switch (c)
{
case'A': {return 0; break; }
case 'C': {return 1; break; }
case'G': {return 2; break; }
case'T': {return 3; break; }
case'-': {return 4; break; }
default:
break;
}
}
int dp[N][N];
string str;//t体会到字符串的好处
int main() {
int n;
cin >>n;
while (n--) {
int n1;
cin >>n1 >>str;
int a[101];
memset(dp, 0, sizeof(dp));
memset(a, -1, sizeof(a));
for (int j = 0; j< n1; j++) {
a[j + 1] = getint(str[j]);
}
int n2;
cin >>n2 >>str;
int b[101];//数组要开大qwq
memset(b, -1, sizeof(b));
for (int j = 0; j< n2; j++) {
b[j + 1] = getint(str[j]);
}
//注意初始化
dp[0][0] = 0;
for (int i = 1; i<= n1; i++) {
dp[i][0] = dp[i - 1][0] + s[a[i]][4];
}
for (int j = 1; j<= n2; j++) {
dp[0][j] = dp[0][j - 1] + s[4][b[j]];
}
for (int i = 1; i<= n1; i++) {
for (int j = 1; j<= n2; j++) {
dp[i][j] = max(dp[i - 1][j - 1] + s[a[i]][b[j]], max(dp[i - 1][j] + s[a[i]][4], dp[i][j - 1] + s[4][b[j]]));
}
}
cout<< dp[n1][n2]<< endl;
}
return 0;
} 8.tug of war（拔河问题）
//tug of war（拔河比赛）重量恰好且数量恰好的的0-1背包问题
//在装载基础上加一个人数的维度
#include#include
#include#includeusing namespace std;
const int maxr = 100;
const int maxc = 10000;
int dp[maxr][maxc];//装j个人，达到k的重量
int a[maxr];
int main() {
int n;
cin >>n;
int total=0;
for (int i = 1; i<= n; i++) {
cin >>a[i]; total += a[i];
}
int sum = total / 2;
int person = ceil(n / 2.0);//向上取整
memset(dp, 0, sizeof(dp));
dp[0][0] = 1;
for (int i = 1; i<= n; i++) {
for (int j = 1; j<= person; j++) {
for (int k = a[i]; k<= sum; k++) {
dp[j][k] = max(dp[j][k], dp[j - 1][k - a[i]]);
}
}
}
int re1 = 0; int re2 = 0;
for (int i = sum; i >= 0; i--) {
if (dp[person][i] || dp[person - 1][i]) {
re1 = i;
re2 = total - re1;
break;
}
}
cout<< re1<< ' '<< re2<< endl; return 0;
} 三、区间DP（遍历型DP）
1.TO Europe
遍历性DP
to europe,遍历上一个分割点的状态
#include#include
#include#include#includeconst int maxn = 99999;
double dp[maxn];
double s[maxn];
int w[maxn];
using namespace std;
int main() {
int b; int l;
int n; int d;
cin >>b >>l >>n;
while (!(b == 0 && l == 0 && n == 0)) {
memset(dp, 0, sizeof(dp));
d = l * 60.0;//以分钟为单位输出
for (int i = 1; i<= n; i++) {
cin >>w[i] >>s[i];
}
dp[0] = 0;
for (int i = 1; i<= n; i++) {
double ans = d / s[i] + dp[i - 1];
int sum = w[i];
double s_min = s[i];
for (int k = i - 1; k >= 1; k--) {
sum += w[k];
s_min = min(s_min, s[k]);
if (sum >b) { break; }//用一个循环遍历考虑到所有情况
//保证小于载重
double temp = d / s_min + dp[k - 1];
ans = min(ans, temp);
}
dp[i] = ans;
}
printf("%.1lf\n", dp[n]);
cin >>b >>l >>n;
}
} 2.multiplication puzzle
//multiplication puzzle
//区间DP，遍历分割点：
#include#include
#includeint n;
const int maxn = 9999;
int dp[maxn][maxn] = { 0 };
int a[maxn] = { 0 };
using namespace std;
int main() {
cin >>n;
for (int i = 0; i< n; i++) {
cin >>a[i];
}
for (int i = 0; i< n; i++) {
dp[i][i] = 0;
}
for (int i = 0; i< n - 1; i++) {
dp[i][i + 1] = 0;
}
for (int l = 2; l<= n - 1; l++) {//循环序列长度
for (int i = 0; i< n - l; i++) {
int j = i + l;
int ans = 1<< 28;
for (int k = i + 1; k< j; k++) {
int v = dp[i][k] + dp[k][j] + a[i] * a[k] * a[j];
ans = min(ans, v);
}
dp[i][j] = ans;
}
}
cout<< dp[0][n - 1]<< endl; return 0;
//} 3.石子归并
解法1
区间dp
石子归并dp[i][j]从i到j合并起来的最小得分
所以其实石子归并也是
#include#include
#includeusing namespace std;
int num, p[301], sum[301], dp[301][301];
int main() {
cin >>num;
for (int i = 1; i<= num; i++) {
cin >>p[i];
}
for (int i = 1; i<= num; i++) {
dp[0][i] = 0;
sum[i] = sum[i - 1] + p[i];
}
//dp[i][j]代表长度为i的序列，j是从第几个石子堆开始合并，最后答案就是dp[num][1]
for (int len = 2; len<= num; len++) {
for (int i = 1; i<= num - len + 1; i++) {
dp[len][i] = 1<< 30;
for (int k = 1; k<= len - 1; k++) {
dp[len][i] = min(dp[len][i], dp[k][i] + dp[len - k][k + i]);
}
dp[len][i] += sum[i + len - 1] - sum[i - 1];
}
}
cout<< dp[num][1]<< endl; return 0;
} 解法2
石子归并：注意和矩阵合并的算法不是很一样要做好区分
#include#include#include
using namespace std;
const int maxn = 100;
int dp[maxn][maxn];
int a[maxn];
int main() {
int n;
cin >>n;
int sum[maxn];
memset(sum, 0, sizeof(sum));
for (int i = 1; i<= n; i++) {
cin >>a[i]; sum[i] = sum[i - 1] + a[i];
}
memset(dp, 0, sizeof(dp));
for (int len = 2; len<= n; len++) {
for (int i = 1; i<= n-len+1; i++) {
int j = i + len - 1;
int ans = 1<< 30;//注意括号j是能取到且必须取到的，这是和上面题的不同
for (int k = i; k< j; k++) {
ans = min(ans, dp[i][k] + dp[k + 1][j]);
}
dp[i][j] = ans + sum[j] - sum[i - 1];
}
}
cout<< dp[1][n]<< endl; return 0;
} 4.环形石子归并
环形石子归并
#include#include
#includeusing namespace std;
const int maxn = 100;
int dp[maxn][maxn];
int a[maxn];
int sum[maxn];
int main() {
//环形输入数组，得到n个合并的大的值
int n;
cin >>n;
for (int i = 1; i<= n; i++) {
cin >>a[i];
a[n + i] = a[i];//多输入一半的数组
}
int sum[maxn * 2];
memset(sum, 0, sizeof(sum));
memset(dp, 0, sizeof(dp));
for (int i = 1; i<= 2 * n; i++) {
sum[i] = sum[i - 1] + a[i];
}
for (int len = 2; len<= n; len++) {
for (int i = 1; i<= 2 * n - len + 1;i++) {
int j = len + i - 1;//i多循环一下
int ans = 1<< 30;
for (int k = i; k< j; k++) {
ans = min(ans, dp[i][k] + dp[k + 1][j]);//
}
dp[i][j] = sum[j] - sum[i - 1] + ans;
}
}
int ret = 1<<28;
for (int i = 0; i<= n; i++) {
ret = min(ret, dp[i + 1][i + n]);
}//最后甄选即可
cout<< ret;
} 5.环形石子归并
//括号匹配：区间DP
#include#include
#include#includeusing namespace std;
const int maxn = 9999;
int dp[maxn][maxn];
string s;
bool match(int i, int j) {//
return(s[i - 1] == '('&&s[j - 1] == ')') || (s[i - 1] == '['&&s[j - 1] == ']');
}
using namespace std;
void print(int x, int y) {//单拿出来print函数又能出一个字符串题+递归题
if (x >y)return;//递归超范围
if (x == y) {//最小化结构单元，统一辽
//最小化边界条件
if (s[x-1] == '(' || s[x-1] == ')') {
cout<< '('<< ')';
}
else
cout<< "[]";
return;//记得终止结尾
}
if (match(x, y)) {
cout<< s[x-1];
print(x+1, y-1);
cout<< s[y-1];
}
for (int k = x; k< y; k++) {
if (dp[x][y] == dp[x][k] + dp[k + 1][y]) {
print(x, k); print(k + 1, y); return;
}
}
}
int main() {
cin >>s;
int len = s.length();
for (int i = 1; i<= len; i++) {
dp[i][i] = 1;//特殊的初始化！！attention！
}
for (int i = 1; i< len; i++) {
dp[i][i + 1] = match(i, i + 1) ? 0 : 2;
}
for (int l = 2; l<= len; l++) {
for (int i = 1; i<= len; i++) {
int j = i + l-1;//这个题里面由于j并无具体的含义，区间or区间端点都可以，所以j的定义很独特
if (j >len)break;
if (match(i, j)) {
dp[i][j] = dp[i + 1][j - 1];
}
else {
dp[i][j] = j - i + 1;
}
for (int k = i; k< j; k++) {
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j]);
}
}
}
//cout<< dp[1][len];
print(1, len);
} 6.最长回文子串和最长回文子序列
//子串：连续的一串序列，子序列：不一定连续
//最长回文子序列：dp[i][j]=max(dp[i][j-1],dp[i+1][j])（if(s[i]!=s[j])else{dp[i][j]=dp[i+1][j-1]+2;}
#include#include
#includeusing namespace std;
const int maxn = 100100;
struct range {
int l;
int r;
int v;
}o[maxn];
int n;
int bin_search(int st, int l, int r) {
int m = (l + r) / 2;
if (o[m].r<= st && o[m + 1].r >st) { return m; }
if (l == m || o[m].r<= st) { return bin_search(st, m + 1, r); }
return bin_search(st, l, m - 1);
}
bool cmp(range a, range b) {
if (a.r == b.r)return a.l< b.l;
return a.r< b.r;
}
int dp[maxn];
int main() {
cin >>n;
int ans = 0; int idx = 0;
for (int i = 1; i<= n; i++) {
cin >>o[i].l >>o[i].r >>o[i].v;
}
memset(dp, 0, sizeof(dp));
sort(o + 1, o + 1 + n, cmp);
for (int i = 1; i<= n; i++) {
idx = bin_search(o[i].l, 0, i);
dp[i] = max(dp[i - 1], dp[idx]+o[i].v);
ans = max(ans, dp[i]);
}cout<< ans<< endl;
} #include#include#includeusing namespace std;
const int maxn = 100;
string s;
int dp[maxn][maxn];
using namespace std;
//此处对回文子串的定义是抽出来多少个，而非一定相同
int main() {
cin >>s;
int len = s.length();
for (int i = 0; i< len; i++) {
dp[i][i] = 1;
}
for (int i = 0; i< len - 1; i++) {
dp[i][i + 1] = s[i] == s[i+1] ? 3 : 2;//单独一个字母也算回文子串
}
for (int l = 2; l< len; l++) {
for (int i = 0; i= len)break;
dp[i][j] = dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1];//上一个括号配对不能同时移动
//如果回文子串定义为抽出若干字母可以构成回文子串：
//if (s[i] == s[j]) {
// dp[i][j] += dp[i + 1][j - 1] + 1;//如果首尾相同，那么每个内部字符串加上外部的字母又会构成新的回文子串
//}
//如果是常规意义必须连续的话，可以判断
if (s[i] == s[j]) {
int a = i; int b = j;
while (s[i] == s[j]) {//顺便也练习了，用while实现递归判断的思路
if (i >= j) { dp[a][b] += 1; break; }//防止i，j改变
i++; j--;
}
}
}
}
cout<< dp[0][len-1];
} 建议配合笔记“食用”~
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
当前标题：计算概论A代码总结Ⅲ（动态规划类）-创新互联
标题来源：http://cdiso.cn/article/cdgogp.html
