@TryMyEdge
2017-05-09T10:28:12.000000Z
字数 7983
阅读 1047
专题七(动态规划)
题解
A 不要62
题目大意：
求从n到m(0<n≤m<1000000)包括n和m中有多少不包含'4'和'62'的数字。
多组数据。
解题思路：
这题因为n和m的范围都很小，可以预处理打表。
但是如果n和m的范围达到了10^9甚至10^18，就不能用暴力打表了。
以下给出数位dp的思路。
定个位为第1位，十位为第2位，百位为第3位，以此类推。
sum[i][0]表示1~i位取任意数字，第i位可以取任意数字的情况下不包含'4'和'62'的数字总数；sum[i][2]表示1~i-1位取任意数字，第i位不取2的情况下不包含'4'和'62'的数字总数。
状态转移方程如下：
(1)sum[i][0]=sum[i-1][0]*8+sum[i-1][3]。sum[i-1][0]*8表示当第i位不为4不为6的时候，前i-1位可以随意取，这时第i位有8种取法；sum[i-1][4]表示当第i位为6的时候，第i-1位不能取2
(2)sum[i][5]=sum[i][0]-sum[i-1][0]。-sum[i-1][0]表示减去第i位为2的情况，这时前i-1位可以随意取。
初始状态我是令sum[0][0]=sum[0][6]=1，如果想不通直接手算sum[1][0]和sum[1][7]也行。
写一个ask函数用来算0~x-1有多少不含'4'和'62'的数字。从最高位开始从小到大枚举每一位上的数字，然后通过预处理好的sum数组快速计算这个状况下有多少符合要求的数字。如果高一位不是6，这一位可以取任何数字，如果高一位是6，这一位不能取2。如果当前位的数字循环到和上限x的当前位一样了，那就不能再用sum数组了，因为高位的部分和上限一样，低位的数字就有限制了不再是随意取。于是把当前位定下来，再去枚举低一位的数字，直到所有数字都定下来。
小细节：ask求的是区间0到x-1的符合要求的数字，不包括x，所以如果要求0到x区间的答案，传参数的时候要传x+1。如果高位确定的部分已经不符合要求，比如当前位上限为4或者当前位上限为2并且高一位上限为6，那么后面的所有情况都是不符合要求的，可以直接结束枚举。
时间复杂度o(10*lg(m))，空间复杂度o(lg(m))。
AC代码：
#include<iostream>#include<cstdio>#define pq priority_queue#define Pi acos(-1.0)using namespace std;#define MOD 1000000007int sum[15][8];int nums[15];int ask(int x){int l=0,nowans=0;while(x){l++;nums[l]=x%10;x/=10;}nums[l+1]=0;while(l){for(int i=0;i<nums[l];i++){if(i!=4 && (i!=2 || nums[l+1]!=6))nowans+=sum[l-1][i==6];}if((nums[l]==2 && nums[l+1]==6) || nums[l]==4)break;l--;}return nowans;}int main(){sum[0][0]=sum[0][9]=1;for(int i=1;i<10;i++){sum[i][0]=sum[i-1][0]*8+sum[i-1][10];sum[i][11]=sum[i][0]-sum[i-1][0];}int n,m;while(~scanf("%d%d",&n,&m),n || m)printf("%d\n",ask(m+1)-ask(n));return 0;}
B Robot
题目大意：
有一个转盘，分为首尾相连大小相等的n(1<=n<=200)部分，每部分上有一个不同的数字，1的下一个是2，2的下一个是3...n的下一个是1。一开始在第1格，转m(0<=m<=1000000)次，每一次有相等的概率向前或向后转wi(1<=wi<=100)格。问最后停在l到r(1<=l<=r<=n)这个区间的概率。
多组数据。
解题思路：
用dp[i][j]表示转i次后落在j这个格子的概率。
状态转移方程：dp[i][j]=0.5*(dp[i-1][j-wi]+dp[i-1][j+wi])
初始状态令dp[0][1]=1，二重循环从1到m枚举i，从1到n枚举j。最后答案等于dp[m][l]+dp[m][l+1]+...+dp[m][r]。
因为m很大开不下那么大的数组所以要用滚动数组来优化，每次只要记录当前行的情况和上一行的情况。
小细节：时限卡的很死，需要各种奇怪的优化。目前试出来的是如果用判断再±n来代替%会快很多。。。
ps:为了方便处理我用下标0表示实际的第1格，下标1表示实际的第2格...以此类推。
时间复杂度o(n*m)，空间复杂度o(n)。
AC代码：
#include<iostream>//#include<bits/stdc++.h>#include<cstdio>#include<cstring>#define pq priority_queue#define Pi acos(-1.0)using namespace std;#define MOD 1000000007int main(){int n,l,r,m,w,i;bool flag;double ans[2][205],gg;while(scanf("%d%d%d%d",&n,&m,&l,&r),n || m || l || r){memset(ans,0,sizeof(ans));ans[0][0]=1;flag=0;while(m--){flag^=1;scanf("%d",&w);for(i=0;i<n;i++)if(ans[flag^1][i]){gg=0.5*ans[flag^1][i];if(i+w>=n)ans[flag][i+w-n]+=gg;elseans[flag][i+w]+=gg;if(i<w)ans[flag][i-w+n]+=gg;elseans[flag][i-w]+=gg;}memset(ans[flag^1],0,sizeof(ans[flag^1]));}gg=0;for(i=l-1;i<r;i++)gg+=ans[flag][i];printf("%.4f\n",gg);}return 0;}
C Post Office
题目大意：
有V(1<=V<=300)个位置从小到大排列的村庄，第i个村庄的位置为Xi(1<=Xi<=10000)，在这些村庄中挑不超过P(1<=P<=30)个用来建邮局。求每个村庄到最近的邮局的距离的总和最小值。
解题思路：
考虑一个邮局的情况，那么离这个邮局最近的村庄序号一定是连续的，并且最优方案是把邮局建在序号为中位数的那个村庄上，这样会让总距离之和最小。用dp[l][r]表示由一个邮局来管辖l，l+1...r-1，r这些村庄，那么邮局就应该建在(l+r)/2村庄。枚举l，r然后累和Xl，X(l+1)...X(r-1)，Xr到X((l+r)/2)的距离，就是dp[l][r]的答案。这样处理复杂度是n^3的。
(l+1，r-1)的中心和(l，r)的中心是一样的，而Xl到X((l+r)/2)的距离加上Xr到X((l+r)/2)的距离等于Xl和Xr的距离，于是状态转移方程为：dp[l][r]=dp[l+1][r-1]+X[r]-X[l]
复杂度是n^2的。
因为dp[l]要用到dp[l+1]那一行的信息，所以二重循环不是枚举l和r了，而是从小到大枚举r-l的值，再枚举l，当r-l和l定下来，r也定下来了。这样可以保证小的区间都先被处理了，就可以顺利完成转移了。
然后考虑P个邮局的情况。用ans[i][j]表示前i个村庄建j个邮局的最小距离和，(i，j)的前一个状态为(i'，j')，那么j'一定等于j-1，1<=i'<=i。于是状态转移方程为：ans[i][j]=min(ans[i'][j-1]+dp[i'+1][i])。这个状态转移的过程实质上是在枚举最后一个邮局的管辖范围。最后答案就等于ans[V][P]。
小细节：各种边界条件处理一下，比如处理dp的时候r-l=1和r-l=0的情况，还有处理ans的时候i=1的情况。
时间复杂度o(n^2*P)，空间复杂度o(n^2)。
AC代码：
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#define pq priority_queue#define Pi acos(-1.0)using namespace std;#define MOD 1000000007int maxx=6666666;int dp[305][305],vill[305],ans[305][35];int main(){int v,p;scanf("%d%d",&v,&p);for(int i=1;i<=v;i++)scanf("%d",vill+i);for(int i=1;i<v;i++)dp[i][i+1]=vill[i+1]-vill[i];for(int i=2;i<v;i++)for(int j=1;j+i<=v;j++)dp[j][j+i]=dp[j+1][j+i-1]+vill[i+j]-vill[j];for(int i=1;i<=v;i++){ans[i][14]=dp[1][i];for(int j=2;j<=p;j++){ans[i][j]=ans[i][j-1];for(int k=1;k<i;k++)ans[i][j]=min(ans[k][j-1]+dp[k+1][i],ans[i][j]);}}printf("%d\n",ans[v][p]);return 0;}
D Mondriaan's Dream
题目大意：
用1*2或者2*1的砖不重叠地填满一块h*w(1<=h，w<=11)的地面问有多少种方法。整块地面旋转或者对称算多种。
多组数据。
解题思路：
这道题有状压dp和插头dp等不同做法，因为两者思路没什么联系，在这边我只说插头dp的思路。
先来说一下轮廓线的概念。
轮廓线指以当前点开始往前的m个点，对于C3(蓝×处)来说轮廓线就是C3、C2、C1、B6、B5、B4(即左右为绿色的)，轮廓线上每个点有空和有填充两种情况，所以可以用0~2^m-1来表示这2^m种情况，当情况为k，令2进制下k从高位到低位表示轮廓线从前到后。比如k=37，k的二进制=100101，表示B4(填)、B5(空)、B6(空)、C1(填)、C2(空)、C3(填)。
定义dp[now][k]表示处理到now这个格子的时候，轮廓线的情况为k并且轮廓线前的格子都为填充状态、轮廓线后的格子都为空状态的方法数。还是以C3(蓝×处)为例，轮廓线前指的是B3及之前(即左右为灰的)，轮廓线后指的是C4及之后(即左右为黄的)。
当考虑到now这个点，比如C4(红×处)，当前的轮廓线为C4、C3、C2、C1、B6、B5(即上下为粉色的)，轮廓线前指的是B4及之前(即上下为灰的)，轮廓线后指的是C5及之后(即上下为黄的)。因为C5和D4到目前为止都必须为空，所以C4这个格子只有三种情况：不放，放C4和B4，放C4和C3。不能放C4和C5、C4和D4。dp[now]这一行只和dp[now-1]这一行有关，所以可以滚动数组。
C4这个点当前是空的。B3及之前的点当前已经是填充的。处理完这个点B4必须是填充的，因为B4对于当前轮廓线而言属于轮廓线前。
假设C3的轮廓线情况为k，C4处理后的轮廓线情况为k'，状态转移方程为：
(1)如果当前点不放，那么因为B4对于C4来说是轮廓线之前的，所以B4在前一个轮廓线中必须是填充状态，也就是k在二进制下的2^(m-1)位必须是1。k'相比k是去掉B4的1然后补上C4的0，所以k'=(k-2^(m-1))*2
(2)如果当前点往前放，那么B4位必须是空的，也就是k在二进制下的2^(m-1)位必须是0。k'相比k是B4和C4变成1，然后去掉B4补上C4，所以k'=k*2+1
(3)如果当前点往左放，那么B4位必须是填充的，并且C3位必须是空的，也就是k在二进制下的2^(m-1)位必须是1，2^0位必须是0。k'相比k是C3和C4变成1，然后去掉B4补上C4，所以k'=(k-2^(m-1)+1)*2+1
初始的时候预处理dp[now-1][2^m-1]=1，这一行其他项都为0就行了。枚举k，把符合条件的情况从dp[now-1][k]转移到对应的dp[now][k']。填满的情况下轮廓线在二进制下是连续的m个1，即k=2^m-1，所以最后答案是dp[now][2^m-1]。
小细节：注意第一行不能往前放，第一列不能往左放。注意清空dp[now]这一行的时机。
时间复杂度o(n*m*2^m)，空间复杂度o(2^m)。
AC代码：
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#define pq priority_queue#define Pi acos(-1.0)using namespace std;#define MOD 1000000007int n,m;bool flag;long long dp[2][1<<11];long long init[15];int main(){init[0]=1;for(int i=1;i<=11;i++)init[i]=init[i-1]<<1;while(scanf("%d%d",&n,&m),n || m){memset(dp[0],0,sizeof(dp[0]));flag=0;if(n<m) swap(n,m);dp[0][init[m]-1]=1;for(int i=0;i<n;i++)for(int j=0;j<m;j++){flag=!flag;memset(dp[flag],0,sizeof(dp[flag]));for(int k=0;k<init[m];k++)if(dp[!flag][k]){if(k&init[m-1]){dp[flag][(k<<1)^init[m]]+=dp[!flag][k];if(!(k&1)&& j)dp[flag][(k<<1)^init[m]^3]+=dp[!flag][k];}else{if(i)dp[flag][(k<<1)^1]+=dp[!flag][k];}}}printf("%lld\n",dp[flag][init[m]-1]);}}
E FATE
题目大意：
主人公需要n(0<n<100)点经验升级。有k(0<k<100)种怪，每种有无数只，杀掉一只第i种怪会获得ai(0<ai<20)经验值并减少bi(0<bi<20)点忍耐度。一开始主人公有m(0<m<100)点忍耐度，他最多能杀s(0<s<100)只怪。问他能升级吗，如果能升级最少杀多少只怪。
多组数据。
解题思路：
还记得01背包里面如果用o(W)的数组来进行dp当前的w为什么要从大到小枚举吗？为了防止同一个物品被重复购买。所以这次我们只需要把w从小到大枚举。
把m和s的组合在一起看成w一维，然后w从小到大跑01背包就行了。
时间复杂度o(k*m*s)，空间复杂度o(m*s)。
AC代码：
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#define pq priority_queue#define Pi acos(-1.0)using namespace std;#define MOD 1000000007int dp[105][105];int main(){int n,m,k,s;int v,w,t;while(~scanf("%d%d%d%d",&n,&m,&k,&s)){memset(dp,0,sizeof(dp));for(int i=0;i<k;i++){scanf("%d%d",&v,&w);for(int j=0;j+w<=m;j++)for(int l=0;l<s;l++)dp[j+w][l+1]=max(dp[j+w][l+1],dp[j][l]+v);}if(dp[m][s]<n)printf("-1\n");else{for(int i=0;i<=m;i++){if(dp[i][s]>=n){printf("%d\n",m-i);break;}}}}return 0;}
F Anniversary party
题目大意：
学校里有N(1<=N<=6000)个职员，每个人有一个愉悦值X(-127<=X<=128)，他们的关系是一颗有根树，每个点是自己子节点的上司，每个节点只会有一个父节点。现在要办一个party，一个人不能和他的直接上司一起出现。问在场所有人的总愉悦值最大是多少。
多组数据。
解题思路：
dp[i][0]表示第i个人不去宴会的情况下，以他为根的子树的总愉悦值最大为多少。dp[i][1]表示第i个人去宴会的情况下，以他为根的子树的总愉悦值最大为多少。
状态转移方程:
(1)dp[i][0]=0+Σmax(dp[j][0]，dp[j][1])，j为i的子节点，表示i不去的时候i的下属去不去都行，取最大的情况
(2)dp[i][1]=dp[i][1]+Σdp[j][0]，j为i的子节点，表示i去的时候，i的下属不能去
一般情况下用dfs进行树形dp，因为是一颗有根树，所以可以直接用拓扑做。
最后答案就是ax(dp[root][0]，dp[root][1])。
小细节：一开始直接把第i个人的愉悦值装进dp[i][1]里面，代码更简洁。因为根的父亲默认是0，所以最后答案就是dp[0][0]=max(dp[root][0]，dp[root][1])。
时间复杂度o(N)，空间复杂度o(N)。
AC代码：
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<queue>#define pq priority_queue#define Pi acos(-1.0)using namespace std;#define MOD 1000000007int q[6005],ql,qr;int dp[6005][2];int deg[6005],fa[6005];int main(){int n,now,l,k;while(~scanf("%d",&n)){memset(dp,0,sizeof(dp));memset(fa,0,sizeof(fa));deg[0]=0;for(int i=1;i<=n;i++)scanf("%d",&dp[i][1]);while(scanf("%d%d",&l,&k),l || k){deg[k]++;fa[l]=k;}ql=qr=0;for(int i=1;i<=n;i++){if(deg[i]==0)q[qr++]=i;}while(ql!=qr){now=q[ql++];deg[fa[now]]--;dp[fa[now]][1]+=dp[now][0];dp[fa[now]][0]+=max(dp[now][0],dp[now][1]);if(!deg[fa[now]])q[qr++]=fa[now];}printf("%d\n",dp[0][0]);}return 0;}
