专题2：动态规划"/>
专题2：动态规划
最近没有打竞赛的心情，因为python太好玩了
问题1：状压dp
题目链接：icpc.upc.edu/problem.php?cid=2196&pid=3
题目大意：
我读了很久才读懂····
首先看看条件约束：
Constraints
·All values in input are integers.
·1≤N≤12
·1≤M≤10^3
·1≤ai≤10^5
·1≤bi≤N
·1≤Ci1<Ci2<...<Cibi≤N
再看输入格式（format）
N M
a1 b1
c11 c12 ... c1b1
:
aM bM
cM1 cM2 ... cMbM
再看提示：
【样例1输入】
2 3
10 1
1
15 1
2
30 2
1 2
【样例1输出】 25
样例1解释
We can unlock all the boxes by purchasing the first and second keys, at the cost of 25 yen, which is the minimum cost required.
再去看看题目
一共有n个盒子，编号为1~n，一共有m把钥匙，每把钥匙买ai元，可以开bi个盒子，是哪bi个盒子呢？是ci1, ci2, ..., cibi。
解题思路
数据量太大，
我肯定只会用dfs死磕，但是大佬说的用状态dp
“现在我们有了表示状态的方法，但心里也会有些不安:上面用十进制表示二进制的数，枚举了全部的状态，DP起来复杂度岂不是很大？没错，状压其实是一种很暴力的算法，因为他需要遍历每个状态，所以将会出现2^n的情况数量，不过这并不代表这种方法不适用：一些题目可以依照题意，排除不合法的方案，使一行的总方案数大大减少从而减少枚举”
.html
状压，其实就是变成二进制来嘛。。。
此代码为模仿大佬写出来的
//#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e4+5;//不能开太大
int A[mod],c[mod],dp[1005][mod];
int main()
{int n,m;scanf("%d %d",&n,&m);for(int i=1;i<=m;i++){int cnt;scanf("%d %d",&A[i],&cnt);int temp=0;for(int j=0;j<cnt;j++){int x;scanf("%d",&x);x--;temp |=(1<<x);}c[i]=temp;}memset(dp,0x3f3f3f3f,sizeof dp);//注意这个地方dp[0][0]=0;for(int i=0;i<m;i++){for(int j=0;j<(1<<n);j++)dp[i+1][j]=dp[i][j];int temp=c[i+1];for(int j=0;j<(1<<n);j++)dp[i+1][ j|temp ]=min( dp[i+1][ j|temp ], dp[i][j] + A[i+1] );}if(dp[m][(1<<n)-1]>=0x3f3f3f3f){printf("-1");return 0;}printf("%d",dp[m][(1<<n)-1]);return 0;
}
此代码为大佬的，我加的注释
//#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e4 + 100;
int n,m,k,ans,h;
int dp[1005][N];
int cost[N],c[N];
int main()
{
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
// ios::sync_with_stdio(false);
// cin.tie(NULL);scanf("%d%d", &n, &m);memset(dp, 0x3f, sizeof dp);dp[0][0] = 0;for (int i = 1; i <= m; ++i){int cnt;scanf("%d%d", cost + i, &cnt);int t = 0;for (int j = 0; j < cnt; ++j){int x;scanf("%d", &x);--x; //因为是从1、2、3...开始的，所以要减去1，不然只有从0、1、2....t |= (1 << x); //1<<x ==x*2 注意：1<<0==1printf("t:%d\n",t);}c[i] = t; //记录的是第i把钥匙能开的门的二进制对应的数字，因为上一步取得是‘|’运算}for (int i = 0; i < m; ++i){for (int j = 0; j < (1 << n); ++j) //自动按二进制来dp[i + 1][j] = dp[i][j];int tmp = c[i + 1];for (int j = 0; j < (1 << n); ++j)dp[i + 1][j | tmp] = min(dp[i + 1][j | tmp], dp[i][j] + cost[i + 1]);}
// printf("%d",0x3f3f3f3f);
// printf("\n%d",0x3f);if (dp[m][(1 << n) - 1] >= 0x3f3f3f3f){puts("-1");return 0;}printf("%d\n", dp[m][(1 << n) - 1]);return 0;
}
第二个问题：线性dp
题目链接：.php?cid=2196&pid=9
题目大意：分成三堆 B1>=B2>=B3 使的B1尽量小
//#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e3 + 100;
int dp[22][1005][670];
int n;
int s[30],sum[30];
int main()
{
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
// ios::sync_with_stdio(false);
// cin.tie(NULL);scanf("%d", &n);dp[0][0][0] = 1;for (int i = 1; i <= n; ++i)scanf("%d", s + i),sum[i] = sum[i - 1] + s[i];int ma1 = sum[n] / 2;int ma2 = sum[n] / 3;for (int i = 0; i < n; ++i)for (int j = 0; j <= ma1; ++j)for (int k = 0; k <= ma2; ++k)if (dp[i][j][k]){dp[i + 1][j][k] = 1;int a = sum[i] - j - k;int b = j;int c = k;b += s[i + 1];if (a < b)swap(a, b); //始终保持 a>bdp[i + 1][b][c] = 1;a = sum[i] - j - k;b = j;c += s[i + 1];if (c > b)swap(b, c);//始终保持 b>cif (b > a)swap(a, b);//始终保持 a>b>cdp[i + 1][b][c] = 1;}int ans = sum[n];for (int i = 1; i <= ma1; ++i)for (int j = 1; j <= ma2; ++j)if (dp[n][i][j])ans = min(ans, sum[n] - i - j);printf("%d\n", ans);return 0;
}
问题3：简单dp类：
问题 O: 采药
时间限制: 1 Sec 内存限制: 128 MB
[提交] [状态]题目描述
辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带 到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时 间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”
如果你是辰辰，你能完成这个任务吗？输入
输入的第一行有两个整数T（1 <= T <= 1000）和M（1 <= M <= 100），用一个空格隔开，T代表总共能够用来采药的时间，M代表山洞里的草药的数目。接下来的M行每行包括两个在1到100之间（包括1和100）的整 数，分别表示采摘某株草药的时间和这株草药的价值。
输出
输出包括一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。
样例输入 Copy
70 3 71 100 69 1 1 2样例输出 Copy
3
题目大意： 简单，略。。
错误代码：
//错误代码
//错误代码
#include <stdio.h>
#include <math.h>
#include <string.h>
int dp[1005][1005];
int a[105][2];
int main()
{int t,m;scanf("%d %d",&t,&m);for(int i=1;i<=m;i++)scanf("%d %d",&a[i][0],&a[i][1]);for(int i=1;i<=m;i++){for(int j=t;j>=a[i][0];j--)dp[i][j]=dp[i-1][j]>dp[i-1][j-a[i][0]]+a[i][1]?dp[i-1][j]:dp[i-1][j-a[i][0]]+a[i][1];}printf("%d",dp[m][t]);}
//AC代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e3+5;
int dp[mod][mod];
int t[mod],v[mod];
int main()
{int T,n;scanf("%d %d",&T,&n);for(int i=1;i<=n;i++)scanf("%d %d",&t[i],&v[i]);for(int i=1;i<=n;i++){for(int j=T;j>=t[i];j--)dp[i][j] = max(dp[i-1][j-t[i]]+v[i],dp[i-1][j]);for(int j=t[i]-1;j>=0;j--)dp[i][j]=dp[i-1][j];}printf("%d",dp[n][T]);return 0;
}
总结：dp问题要确定好下一步与上一步的对应关系。
问题3：
问题 L: Payment
时间限制: 1 Sec 内存限制: 128 MB
[提交] [状态]题目描述
In the Kingdom of AtCoder, only banknotes are used as currency. There are 10100+1 kinds of banknotes, with the values of 1,10,102,103,…,10(10^100). You have come shopping at a mall and are now buying a takoyaki machine with a value of N. (Takoyaki is the name of a Japanese snack.)
To make the payment, you will choose some amount of money which is at least N and give it to the clerk. Then, the clerk gives you back the change, which is the amount of money you give minus N.
What will be the minimum possible number of total banknotes used by you and the clerk, when both choose the combination of banknotes to minimize this count?
Assume that you have sufficient numbers of banknotes, and so does the clerk.
Constraints
·N is an integer between 1 and 101,000,000 (inclusive).
输入
Input is given from Standard Input in the following format:
N输出
Print the minimum possible number of total banknotes used by you and the clerk.
样例输入 Copy
【样例1】 36 【样例2】 91 【样例3】 314159265358979323846264338327950288419716939937551058209749445923078164062862089986280348253421170样例输出 Copy
【样例1】 8 【样例2】 3 【样例3】 243提示
样例1解释
If you give four banknotes of value 10 each, and the clerk gives you back four banknotes of value 1 each, a total of eight banknotes are used.
The payment cannot be made with less than eight banknotes in total, so the answer is 8.
样例2解释If you give two banknotes of value 100,1, and the clerk gives you back one banknote of value 10, a total of three banknotes are used.
自己模拟一下这个过程就能理解代码了，思路需要积累
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int mod=1000005;
ll dp[mod][5];
char str[mod];
int main()
{str[0]='0';scanf("%s",str+1);int n=strlen(str+1);dp[n][0]=str[n]-'0';dp[n][1]=1+9-(str[n]-'0');for(int i=n-1;i>=0;i--){dp[i][0]=min(dp[i+1][0]+str[i]-'0',dp[i+1][1]+str[i]-'0'+1);dp[i][1]=min(dp[i+1][0]+10-str[i]+'0',dp[i+1][1]+10-str[i]+'0'-1);//dp[i][0]是给刚好，dp[i][1]是给大的找}printf("%lld",min(dp[0][0],dp[0][1]));return 0;
}/**************************************************************Problem: 14662User: 2019UPC110Language: C++Result: 正确Time:56 msMemory:42064 kb
****************************************************************/非常简单的动态规划
问题 A: 变音量
时间限制: 1 Sec 内存限制: 128 MB
[提交] [状态]题目描述
你将要在元旦演奏一场吉他专场。但你不希望声音平淡，所以你希望每个曲之间都有变化。现在你已经确定了每个曲可以与上一个曲之间的音量的变化量，即每首曲开始，你可以对音量选择增加或减少一个指定的变化值。当然音量不可能为负数，也不能太高，因此必需保证每首曲音量在0和maxLevel之间（包含）。
你的任务是，根据已有的开始音量beginLevel 和每首曲之间的变化量，求出最后一首曲的最大可能音量。如果没有方案，输出 -1。
输入
第一行有三个整数，n, beginLevel, maxLevel，分别表示曲目数，开始量，最大限制音量。
下面有n-1行整数，第i行整数表示第i首曲与第i+1首曲之间的变化量。
输出
只一行一个数，答案。
样例输入 Copy
【样例1】 4 5 10 5 3 7 【样例2】 5 8 20 15 2 9 10样例输出 Copy
【样例1】 10 【样例2】 -1提示
1<=n<=60;
1<= maxLevel <=1000
0<= beginLevel <= maxLevel
区别dfs与动态规划：
对样例1 的分析：
//0 1 2 3 4 5 6 7 8 9 10
// 1
//1 1
// 1 1
//1 1
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const double eps=1e-6;
const double pi=cos(-1);
const int N=1e5+5;
const int mod=1e9+7;
int a[100];
int n,bl,ml,ans=-1;
void dfs(int now,int s)
{if(ans==ml) return ;if(s>=n){ans=max(now,ans);return ;}if(now+a[s]<=ml)dfs(now+a[s],s+1);if(now-a[s]>=0)dfs(now-a[s],s+1);return ;
}
int main()
{scanf("%d%d%d",&n,&bl,&ml);for(int i=1; i<n; i++)scanf("%d",a+i);dfs(bl,1);printf("%d",ans);return 0;
}/**************************************************************Problem: 14885User: 2019UPC110Language: C++Result: 时间超限
****************************************************************/
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const double eps=1e-6;
const double pi=cos(-1);
const int N=1e5+5;
const int mod=1e9+7;
int dp[65][1005],a[65];
int n,bl,ml;
int main()
{scanf("%d%d%d",&n,&bl,&ml);for(int i=1;i<n;i++){scanf("%d",&a[i]);}dp[1][bl]=1;for(int i=1;i<n;i++){for(int j=0;j<=ml;j++){if(j+a[i]<=ml) dp[i+1][j+a[i]]=max(dp[i][j],dp[i+1][j+a[i]]);if(j-a[i]>=0) dp[i+1][j-a[i]]=max(dp[i][j],dp[i+1][j-a[i]]);}}int ans=-1;for(int i=ml;i>=0;i--){if(dp[n][i]){ans=i;break;}}printf("%d",ans);return 0;
}
//0 1 2 3 4 5 6 7 8 9 10
// 1
//1 1
// 1 1
//1 1/**************************************************************Problem: 14885User: 2019UPC110Language: C++Result: 正确Time:2 msMemory:2280 kb
****************************************************************/
问题 E: 圣诞岛的走廊
时间限制: 1 Sec 内存限制: 128 MB
[提交] [状态]
题目描述
下了飞机，Angel走到了一个奇怪的走廊里。走廊非常的窄，只有2格宽，但是却很长。Angel想尽快走出这个走廊，你能帮他吗？
走廊有n(n<=10,000)行，但是只有2列。走廊中有一些格子不能被通过，从一个格子移动到上、下、左、右的相邻格子需要1单位时间。问Angel最少什么时候达到第n行？假设Angel一开始在左上角(第1行)。
输入
第一行n，然后n行，每行两个数字，0代表能通过，1代表不能通过。
输出
输出一行，代表最少需要的时间。
如果永远不能到达，输出一行Poor。
样例输入 Copy
5 0 0 1 0 0 0 0 1 0 0
样例输出 Copy
6
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 500;
const int mod = 10007;
priority_queue<ll,vector<ll>,greater<ll>>q;
int a[10005][5];
int dp[10005][5];
int main()
{int n;scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d%d",&a[i][1],&a[i][2]);for(int i=1;i<=n;i++)dp[i][1]=1000000,dp[i][2]=1000000;//printf("%d\n",dp[1][1]);if(a[1][2]==0) dp[1][2]=1;dp[1][1]=0;//printf("%d\n",dp[1][1]);for(int i=2;i<=n;i++){if(a[i][1]==0){if(a[i-1][1]==0)dp[i][1]=min(dp[i-1][1]+1,dp[i][1]) ;if(a[i][2]==0)dp[i][1]=min(dp[i][2]+1,dp[i][1]);}if(a[i][2]==0){if(a[i-1][2]==0)dp[i][2]=min(dp[i-1][2]+1,dp[i][2]) ;if(a[i][1]==0)dp[i][2]=min(dp[i][1]+1,dp[i][2]);}if(a[i][1]==0){if(a[i-1][1]==0)dp[i][1]=min(dp[i-1][1]+1,dp[i][1]) ;if(a[i][2]==0)dp[i][1]=min(dp[i][2]+1,dp[i][1]);}if(a[i][2]==0){if(a[i-1][2]==0)dp[i][2]=min(dp[i-1][2]+1,dp[i][2]) ;if(a[i][1]==0)dp[i][2]=min(dp[i][1]+1,dp[i][2]);}}int ans=min(dp[n][1],dp[n][2]);if(ans>=1000000) printf("Poor");else printf("%d",ans);return 0;
}
更多推荐
专题2：动态规划
发布评论