定制产品网站有哪些,动漫做暧昧视频网站,win10一键优化工具,重庆建站服务商记
2018年3月19日
贼颓呢#xff0c;一天就写了两道DP#xff0c;还都不会写#xff0c;这可GG。 动态规划真的难且有趣#xff0c;算法题中动态规划占到了很大的比例#xff0c;而且动态规划往往是辅助解决一些其他类型问题的基础#xff0c;加深加强对动态规划问题的…记
2018年3月19日
贼颓呢一天就写了两道DP还都不会写这可GG。 动态规划真的难且有趣算法题中动态规划占到了很大的比例而且动态规划往往是辅助解决一些其他类型问题的基础加深加强对动态规划问题的认识和训练非常有必要。
P2577 午餐
题意
题意见题目链接
题解
这道题目本质上是一道背包问题是背包问题的变形,这道题不同的地方在于有两个背包。 因此我们设计状态的时候两个背包的状态都要记录。
贪心
由于每个队列的排队顺序不一样结果也是不一样的。而可以证明当把所有的同学按照其吃饭时间降序排序的话这样的排队顺序一定是最优的顺序。
朴素
我们最初想到的状态是这样的 dp[i][j][k]dp[i][j][k]dp[i][j][k]表示当前考虑的是前i个人已经被分配且第一个队列排队打饭时间和为i第二个队列排队打饭的时间和为j最早的集合时间。 那么转移方程可以写成 dp[i][j][k]min(max(dp[i−1][j−a[i]][j],jb[i]),max(dp[i−1][j][k−a[i]],kb[i]))dp[i][j][k]min(max(dp[i−1][j−a[i]][j],jb[i]),max(dp[i−1][j][k−a[i]],kb[i]))dp[i][j][k] = min(max(dp[i-1][j-a[i]][j],j+b[i]),max(dp[i-1][j][k-a[i]],k+b[i])) 转移方法把i分给第1个窗口或者把i分给第2个窗口。
显然这样时间、空间复杂度会爆炸。 空间复杂度为O(2005)O(2005)O(200^5)
优化
因此我们必须优化进一步挖掘条件以降维。 我们发现jksumb[i]jksumb[i]j+k = sumb[i] 这样的话我们直接可以减少一维定义 dp[i][j]dp[i][j]dp[i][j]表示考虑前i个人第一个窗口的同学总打饭时间为j时候前i个同学最早集合的时间。 空间复杂度变成了O(2003)O(2003)O(200^3) 转移方程: dp[i][j]min(max(dp[i−1][j−a[i]],jb[i]),max(dp[i−1][j],sumb[i]−jb[i]))dp[i][j]min(max(dp[i−1][j−a[i]],jb[i]),max(dp[i−1][j],sumb[i]−jb[i]))dp[i][j] = min(max(dp[i-1][j-a[i]],j+b[i]),max(dp[i-1][j],sumb[i]-j+b[i]))
进一步优化
由于我们发现i状态的转移只与i-1有关系因此我们可以用滚动数组继续优化掉一维。 时间复杂度O(2002)O(2002)O(200^2) 总的时间复杂度为O(2003)O(2003)O(200^3)
细节
注意边界条件以及转移成立的条件。
代码
#include iostream
#include cstdio
#include algorithm
#include cstring
using namespace std;
typedef pairint,int pii;
const int maxn 205;
const int inf 0x3f3f3f3f;
pii ps[maxn];
int dp[2][maxn*maxn],sum[maxn];
int n;
int main(){memset(dp,0x3f,sizeof(dp));scanf(%d,n);for(int i 0;i n;i){int a,b;scanf(%d%d,a,b);ps[i1] make_pair(-b,a);}sort(ps1,ps1n);dp[0][0] 0;for(int i 1;i n;i){memset(dp[i1],0x3f,sizeof(dp[i1]));sum[i] sum[i-1] ps[i].second;for(int j 0;j sum[i];j){if(j ps[i].second)dp[i1][j] min(dp[i1][j],max(dp[(i-1)1][j-ps[i].second],j-ps[i].first));if(sum[i]-j ps[i].second)dp[i1][j] min(dp[i1][j],max(dp[(i-1)1][j],sum[i]-j-ps[i].first));}}int mi inf;for(int j 0;j sum[n];j){if(dp[n1][j] mi){mi dp[n1][j];}}coutmiendl;return 0;
} P1070道路游戏
题意
题目链接看题意
题解
这道题本质上就是在下图斜线上的dp。
Column表示机器人出售站。 Row表示时间轴。 字母相同的斜线上相邻的两个表格表示由上一个表格的数字下一步将取到下面表格的数字。 这样就相当于我们把整个表格横着切几段然后每一段内部选一条连续的斜线并把斜线里的数字加起来减去该段斜线第一个站点的费用。把所有的段的值加起来得到一个新的数值我们要做的就是最大化这个数值。 定义状态 opt[i]opt[i]opt[i]表示前i行所能收集的最大金币值。 sum[i][j]sum[i][j]sum[i][j]表示从第一行的第i站出发沿着斜线走一共收集j格的金币得到的总和。
那么状态转移方程就是 iii表示行，j" role="presentation" style="position: relative;">jjj表示机器人购买点所在的斜线编号。 kkk表示上一次刚好停在哪一行。
opt[i]=max(opt[k]+sum[j][i]#x2212;sum[j][k]#x2212;cost[j+k]),1lt;=klt;=p" role="presentation" style="position: relative;">opt[i]=max(opt[k]+sum[j][i]−sum[j][k]−cost[j+k]),1=k=popt[i]=max(opt[k]+sum[j][i]−sum[j][k]−cost[j+k]),1=k=popt[i] = max(opt[k]+sum[j][i]-sum[j][k]-cost[j+k]),1 解释为什么costcostcost的下标是jkjkj+k: 因为j表示的斜线编号在第k1行买机器人实际的购买站点是jk 这样做的话时间复杂度是O(n∗m∗p)O(n∗m∗p)O(n*m*p)不满足要求因此我们必须继续优化。 看着形式我就只能想到单调队列或者是斜率优化了这道题单调队列优化显然是可以的。 我们i,j循环变量不能省略能省略的就只有k了。我们把i和j与k分离开 opt[i]max(sum[j][i](opt[k]−sum[j][k]−cost[jk])),1kpopt[i]max(sum[j][i](opt[k]−sum[j][k]−cost[jk])),1kpopt[i] = max(sum[j][i]+(opt[k]-sum[j][k]-cost[j+k])),1 分离出来的这部分 (opt[k]−sum[j][k]−cost[jk])(opt[k]−sum[j][k]−cost[jk])(opt[k]-sum[j][k]-cost[j+k]) 就只与kkk和j" role="presentation" style="position: relative;">jjj有关了因此我们可以建立nnn个单调队列对应j" role="presentation" style="position: relative;">jjj队列内部对应kkk。dp核心代码for(int i = 1;i = m;++i){//i表示时刻for(int j = 1;j = n;++j){//j表示机器人的购买点所在的斜线编号while(PQS[j].size() i-PQS[j].getfront().first p) PQS[j].pop();pii p = PQS[j].getfront();opt[i] = max(opt[i],sum[j][i] + p.second);}for(int j = 1;j = n;++j){int pre = j+i;while(pre n) pre -= n;PQS[j].push(i,opt[i] - sum[j][i] - cost[pre]);}}总的代码#include iostream
#include cstdio
#include cstring
using namespace std;
const int maxn = 1005;
typedef pairint,int pii;struct PQ{pii ps[maxn];int front,tail;void push(int idx,int key){while(tail front key = ps[tail-1].second)tail--;ps[tail++] = make_pair(idx,key);}void pop(){if(front tail) ++front;}int size(){return tail-front;}pii getfront(){return ps[front];}
}PQS[maxn];int n,m,p;
int val[maxn][maxn];
int sum[maxn][maxn];//1:出发点 2: 步数
int opt[maxn];
int cost[maxn];
const int inf = 1e9;
int main(){scanf("%d%d%d",n,m,p);for(int i = 1;i = n;++i){for(int j = 1;j = m;++j){scanf("%d",val[i][j]);}}for(int i = 1;i = n;++i){scanf("%d",cost[i]);}for(int i = 1;i = n;++i){int pre = i-1;for(int j = 1;j = m;++j){if(++pre == n+1) pre = 1;sum[i][j] = sum[i][j-1]+val[pre][j];//printf("i:%d,j:%d,sum:%d\n",i,j,sum[i][j]);}}for(int i = 1;i = n;++i)PQS[i].push(0,-cost[i]); for(int i = 1;i = m;++i)opt[i] = -inf;//dpfor(int i = 1;i = m;++i){//i表示时刻for(int j = 1;j = n;++j){//j表示机器人购买点所在的斜线编号while(PQS[j].size() i-PQS[j].getfront().first p) PQS[j].pop();pii p = PQS[j].getfront();opt[i] = max(opt[i],sum[j][i] + p.second);}for(int j = 1;j = n;++j){int pre = j+i;while(pre n) pre -= n;PQS[j].push(i,opt[i] - sum[j][i] - cost[pre]);}}coutopt[m]endl;return 0;
}P2051 中国象棋题意点击链接查原题目题解我好菜啊，这道是原题，暑假集训的时候做过，而且当时还独自做出来了，过了半年，自己再做的时候发现竟然不会做了，看了题解的提示才想出来。咋越练越菜呢？？？
这道题目关键点在状态的定义！我们需要把无用的信息都去除掉，在状态定义的时候尽量捕捉最本质、最关键的信息。
例如本题，按行考虑，在考虑到第i行的时候，我们关注点在前i行中，形成的0炮列有几个，1个炮的列有几个，2个跑的列有几个，这样。
而我们不需要知道具体的前i行的棋子排列。状态定义就出来了：
dp[i][j][k]" role="presentation" style="position: relative;">dp[i][j][k]dp[i][j][k]dp[i][j][k]表示前i行构成有j个1炮列、k个2炮列可行的方案数。 这样的话转移方程也很容易得到就是乘法原理。
注意分类的时候这样分 第i行不加棋子的转移、加1个棋子的转移、加2个棋子的转移。
加1个棋子的转移又可以分为把这个棋子加到0炮列把这个棋子加到1炮列。
加2个棋子的转移又可以分为全都加到0炮列、全都加到1炮列、0炮列1炮列分别加一个。
按照这样分类转移转移方程很好写。
代码
#include iostream
#include cstdio
using namespace std;
typedef long long ll;
ll n,m;
const int maxn 106;
const ll mod 9999973;
ll dp[maxn][maxn][maxn];
int main(){cinnm;dp[1][0][0] 1;dp[1][1][0] m;dp[1][2][0] m*(m-1)/2;for(int i 2;i n;i){for(int j 0;j m;j){for(int k 0;kj m;k){//0dp[i][j][k] dp[i-1][j][k];//1if(j 1){ll p m - k - (j-1);dp[i][j][k] dp[i-1][j-1][k]*p%mod;dp[i][j][k] % mod;}if(k-1 0){dp[i][j][k] dp[i-1][j1][k-1]*(j1)%mod;dp[i][j][k] % mod;}//2if(j 2){ll p (m-k-j2);p p*(p-1)/2%mod;dp[i][j][k] dp[i-1][j-2][k]*p%mod;dp[i][j][k] % mod;}if(k 2){ll p (j2)*(j1)/2%mod;dp[i][j][k] dp[i-1][j2][k-2]*p%mod;dp[i][j][k] % mod;}if(k 1){ll p m - j - (k-1);dp[i][j][k] dp[i-1][j][k-1]*j*p%mod;dp[i][j][k] % mod;}//dp[i][j][k] }}}ll ans 0;for(int i 0;i m;i){for(int j 0;ji m;j){ans (ans dp[n][i][j])%mod;}}coutansendl;
}
