2021/09/06_基础DP例题复习(1)
2021/09/06 A.M. 7:40-10:40
| Problems | Pebble | Compete | Hall | Message | Escape | Game | Traffic | Lcs | Toy | Lcis |
| 预估分数 | 100 | 30 | 100 | 100 | 0 | 100 | 100 | 100 | 0 | 100 |
| 实际分数 | 100 | 100 | 100 | 100 | 0 | 100 | 100 | 0 | 0 | 100 |
解题报告
A:Pebble_石子合并
非常经典的一道区间DP例题。
从区间长度着手处理：先枚举区间长度，再对端点进行枚举，最后对区间中断点枚举即可。
dp_min[l][r]表示合并第l颗石子到第r颗石子的区间的最小得分。
令k为该区间中的断点，那l到r的最小得分由两种途径得来：
1：由两堆已经合并的石子，即一堆为l到k、另一堆为k+1到r合并得来；
2：由之前该区间已算出的得分得来。
在两者中取小者。
dp_max[l][r]同理。
sum[i]表示
转移方程如下：
dp_min[l][r]=min(dp_min[l][k]+dp_min[k+1][r]+sum[r]-sum[l-1],dp_min[l][r]), dp_max[l][r]=max(dp_max[l][k]+dp_max[k+1][r]+sum[r]-sum[l-1],dp_max[l][r]);
本题的石子是环形摆放，那么也就意味着最优解的起点可能不是第1颗石子，就需要将环展开，并延长一倍，从合并第i颗石子到第i+n-1颗石子的得分中取最值。
#include<stdio.h> #include<iostream> #include<string.h> using namespace std; int n,a[201],ansmx,ansmn; int dpmn[201][201],dpmx[201][201]; int sum[201]; int main(){ memset(dpmn,0x3f3f3f3f,sizeof(dpmn)); ansmn=0x3f3f3f3f; scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",a+i),a[i+n]=a[i]; for(int i=1;i<=(n<<1);++i) sum[i]=sum[i-1]+a[i], dpmx[i][i]=dpmn[i][i]=0, dpmx[i][i+1]=dpmn[i][i+1]=a[i]+a[i+1]; for(int len=2;len<=n;++len) for(int l=1;l<=n*2-len;++l){ int r=l+len-1; for(int k=l;k<r;++k) dpmx[l][r]=max(dpmx[l][k]+dpmx[k+1][r]+sum[r]-sum[l-1],dpmx[l][r]), dpmn[l][r]=min(dpmn[l][k]+dpmn[k+1][r]+sum[r]-sum[l-1],dpmn[l][r]); } for(int i=1;i<=n;i++) ansmx=max(ansmx,dpmx[i][i+n-1]), ansmn=min(ansmn,dpmn[i][i+n-1]); printf("%d\n%d",ansmn,ansmx); }
B:Compete_对抗赛
题目描述 程序设计对抗赛设有 N（0<N≤50 的整数）个价值互不相同的奖品，每个奖品的价值分别为 S1，S2，S3……Sn（均为不超过 100 的正整数）。现将它们分给甲乙两队，为了使得甲乙两队得到相同价值的奖品，必须将这 N 个奖品分成总价值相等的两组。 编程要求：对给定 N 及 N 个奖品的价值，求出将这 N 个奖品分成价值相等的两组，共有多少种分法？ 例如：N = 5，S1，S2，S3……Sn 分别为 1，3，5，8，9 则可分为{1，3，9}与{5，8} 仅有 1 种分法； 例如：N = 7，S1，S2，S3……Sn 分别为 1，2，3，4，5，6，7 则可分为： {1,6,7}与{2,3,4,5} {2,5,7}与{1,3,4,6} {3,4,7}与{1,2,5,6} {1,2,4,7}与{3,5,6} 有4种分法。 输入 第一行一个整数N； 第二行N个数据：S1，S2，S3……Sn，每两个相邻的数据之间有一个空格隔开。 输出 一行一个整数，表示有多少种分法。无解输出0。
题意可转化为给出和为Sum的N个数，从中任选若干数，求有多少种选法使得选出数之和等于Sum/2。
可是本蒟蒻第一反应竟然是DFS，害，看来我没救了。但数据也是很水，用了个剪枝搜索就过了。
void Dfs(int pos,int tot){//pos是当前可选数的下标，tot是之前已选数之和 if(pos==n){//到达边界 ans+=(tot==sum); return; } if(tot>sum)return;//当前总和已经超过Sum/2 if(tot==sum){//找到一种情况 ans++;return; } Dfs(pos+1,tot+a[pos]);//选择当前数，继续搜索 Dfs(pos+1,tot);//不选择当前数，继续搜索 }
上正解：
本题就是简单的背包问题。每个数为物品，其值为质量，而Sum/2即是背包大小。
for(int i=1;i<=n;++i){ scanf("%d",a+i); sum+=a[i]; } if(sum%2)return(printf("0")&&0);//数的总和为奇数，无解 sum>>=1; dp[0]=1; for(int i=1;i<=n;++i) for(int v=sum;v>=a[i];--v) dp[v]+=dp[v-a[i]];//简单的背包，dp[v]表示总和为v的情况数量 printf("%d",dp[sum]/2);//对于{1,6,7}与{2,3,4,5}这样一种可行的方案，分为两部分后分别被计算了两遍，故除以2 }
C:Hall_演讲大厅安排
题目描述 有一个演讲大厅需要我们管理，演讲者们事先定好了需要演讲的起始时间和中止时间。我们想让演讲大厅得到最大可能的使用。我们要接受一些预定而拒绝其他的预定，目标是使演讲者使用大厅的时间最长。假设在某一时刻一个演讲结束，另一个演讲就可以立即开始。 编程任务： 1、输入入演讲者的申请。 2、计算演讲大厅最大可能的使用时间。 3、输出结果。 输入 第一行为一个整数 N，N≤5000，表示申请的数目。 以下 n 行每行包含两个整数 p，k，1 ≤ p < k ≤ 30000，表示这个申请的起始时间和中止时间。 输出 一个整数，表示大厅最大可能的使用时间。 样例输入 12 1 2 3 5 0 4 6 8 7 13 4 6 9 10 9 12 11 14 15 19 14 16 18 20 样例输出 16
很容易想到，用一个结构体来存演讲者的开始时间（a[i].l）和结束时间（a[i].r），再按开始时间（a[i].l）对演讲者进行排序。
接着动态规划：a[i].time记录第i个人演讲结束时大厅的最大使用时间，由他前面的演讲者j(1<=j<i)转移过来。为保证演讲者i开始演讲时上一位演讲者已经演讲结束，演讲者j需要满足的条件：a[j].r<=a[i].l。
转移方程如下:
a[i].time=max(a[i].t+a[j].time,a[i].time);
为什么按照开始时间（a[i].l）排序之后的动态规划一定是最优解？因为第i个演讲者不可能在演讲者k(i<k<=n)之后演讲，只可能在演讲者j(1<=j<i)之后。
D:Message_传纸条
NOIp原题，典型的棋盘DP。
一般最容易想到的是四维DP，两条路线来回转化为相同起点与相同终点的两条路。用dp[x1][y1][x2][y2]表示第一张纸条传到(x1,y1)，第二张纸条传到(x2,y2)的好心程度和。
每张纸条只会向下或向右传，故对于每次转移，共有四种情况：下下，下右，右下，下下。
故转移方程为：
dp[i][j]=max(dp[i-1][j][p-1][q] ,dp[i-1][j][p][q-1] ,dp[i][j-1][p-1][q] ,dp[i-1][j][p][q-1])+a[i][j]+a[p][q];
这样时间复杂度O(n^4)。
如何优化呢？
很容易发现，两张纸条每次都只会向右或向下传一个格点，且时刻相同，两条路径长度相等，除起点和终点之外的时刻不相交。那么意味着两张纸条同一时刻行数与列数分别不相同。
由此将DP压缩成三维：dp[p][i][j]表示当前走了p步，第一张纸条走到第i行，第二张纸条走到第j行的最大值。
转移方程如下：
dp[p][i][j]=max(max(dp[p-1][i][j],dp[p-1][i-1][j]),max(dp[p-1][i][j-1],dp[p-1][i-1][j-1]))+a[i][p-i+1]+a[j][p-j+1];
判重：当(i==j)时两纸条位于同一格点，该点的权值只能被计算一次，故：
if(i==j) dp[p][i][j]+=a[i][p-i+1]; else dp[p][i][j]+=a[i][p-i+1]+a[j][p-j+1];
E:Escape_守望者的逃离
第一反应就是小学数学？虽然但是，我可能没上过小学好吧。
看到题解悟了呀，基于时间轴的线性DP。S1和S2分别存放跑步能走的距离和用闪现能走的距离。
for(int i=1;i<=t;++i){ S1+=17;//只考虑跑步的情况 if(m>=10) S2+=60,m-=10;//S2优先闪现 else m+=4;//魔法不足，恢复魔法 if(S2>S1) S1=S2;//如果闪现当前闪现快于跑步则更新距离 if(S1>S) return(printf("YES\n%d",i)&&0); } return(printf("NO\n%d",S1)&&0);
F:Game_矩阵取数游戏
NOIp原题，经典DP。
设dp[l][l+len][i]表示在第i行取数，左端点为l，右端点为l+len所能获得的最大值。
直接上转移方程了：
dp[l][l+len][i]=max(dp[l+1][l+len][i]+a[i][l],dp[l][l+len-1][i]+a[i][l+len])>>1;
估算题目计算不超过(2^100)，所以第一次直接拿_int128过了。
但是很显然正解是要求我们打高精的（可蒟蒻打不来啊啊啊）。
在洛谷看到一个高精题解，感觉蛮好看的：
#include<iostream> #include<cstring> #include<algorithm> #include<cstdio> #define A 1000000000000000 using namespace std; struct bint{ long long s[10]; bint(long long num=0){ *this=num; } bint operator=(long long num){ memset(s,0,sizeof(s)); s[0]=num; return*this; } bint operator+(const bint&b)const{ bint c; unsigned long long g=0; for(int i=0;i<9;i++){ unsigned long long x=g; x+=(unsigned long long)s[i]+b.s[i]; c.s[i]=x%A; g=x/A; } return c; } bint operator*(const bint&b)const{ bint c; unsigned long long g=0; for(int i=0;i<9;i++){ unsigned long long x=g; for(int j=0;j<=i;j++){ int k=i-j; x+=(unsigned long long)s[k]*b.s[j]; } c.s[i]=x%A; g=x/A; } return c; } bool operator <(const bint& b)const{ for(int i=9;i>=0;i--){ if(s[i]<b.s[i])return 1; if(s[i]>b.s[i])return 0; } return 0; } void print(){ char buf[200]; for(int i=9;i>=0;i--) sprintf(buf+(9-i)*15,"%015lld",s[i]); bool flag=0; for(int i=0;i<150;i++){ if(buf[i]>\'0\')flag=1; if(flag)printf("%c",buf[i]); } if(!flag)printf("0"); } }; long long a[100];bint dp[100][100]; bint ans; bint two[82]; inline void init(){ two[0]=1; for(int i=1;i<=80;i++) two[i]=two[i-1]*2; } bint at[100][100]; bool used[100][100]; inline bint multi(int i,int p){ if(used[i][p])return at[i][p]; used[i][p]=true; return at[i][p]=(bint)a[i]*two[p]; } int main(){ init(); int n,m; cin>>n>>m; ans=0; for(int w=0;w<n;w++){ memset(dp,0,sizeof(dp)); memset(used,false,sizeof(used)); for(int i=1;i<=m;i++)scanf("%d",a+i); bint anst=0; for(int t=0;t<m;t++){ for(int i=1;i+t<=m;i++){ int j=i+t; int p=m-t; bint s=dp[i+1][j]+multi(i,p); bint t=dp[i][j-1]+multi(j,p); if(s<t)dp[i][j]=t; else dp[i][j]=s; } } ans=ans+dp[1][m]; } ans.print(); cout<<endl; }
G:Traffic_城市规划
动态规划的入门题咯，或者是跑一遍最短路也行，我直接上Floyd算法。
唯一注意一下的点就是只能从编号小的点到编号大的点。
H:Lcs_最长公共子序列
线性DP经典例题。
转移方程：
if(a[i]==b[j])f[i][j]=dp[i-1][j-1]+1; else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
然而我WA了？回头看题面内存限制，啊，是64MB，那没事了。
那就要滚动数组了。
因为每个长度的状态只会由前一次的状态转移而来，所以只需要dp[2][MAXN]即可。
当然，通过取模或者是01异或都可以。
for(int i=1;i<=la;i++){ for(int j=1;j<=lb;j++) if(a[i]==b[j])dp[z][j]=dp[z^1][j-1]+1; else dp[z][j]=max(dp[z^1][j],dp[z][j-1]); z^=1; }
H:Toy_玩具装箱
“这是一道经典的斜率优化入门题。”好吧不会斜率优化的小蒟蒻我看到这道题数据开始怀疑是不是动态规划。
于是赶去洛谷向大佬们学习了一番，额，但是还是好懵。
这道题暂留，关于斜率优化的还待学习啦。
I:Lcis_最长公共上升子序列
线性DP例题。结合Lis和Lcs，容易得到转移方程：
if(a[i]==b[j]) dp[i][j]=max(dp[i-1][k]+1)//(1<=k<=j-1&&b[j]>b[k]) else dp[i][j]=dp[i-1][j]
for(int i=1;i<=n;i++){ int val=0;//val是决策集合S(i,j)中dp[i-1][k]的最大值 for(int j=1;j<=n;j++) f[i][j]=(a[i]==b[j]?val+1:f[i-1][j]), val=b[j]<a[i]?max(val,f[i-1][j]):val; } for(int j=1;j<=n;j++)ans=max(ans,f[n][j]);
最后安利一首MILABO-ずっと真夜中でいいのに。
（尝试夹带私货啊哈哈哈）
