外贸网站模板制作,做网站为什么很复杂,wordpress环保公司主题,如何提高网站pr值记
练习一下动态规划水题系列#xff0c;防止脑子生锈。
P1879 玉米田
题解
非常典型的状态压缩DPDP#xff0c;先预处理出所有可行的状态SS。
然后逐行DP role=presentation style=position: relative;DPDP#xff0c;定义状态dp[i…记
练习一下动态规划水题系列防止脑子生锈。
P1879 玉米田
题解
非常典型的状态压缩DPDPDP先预处理出所有可行的状态SSS。
然后逐行DP" role="presentation" style="position: relative;">DPDPDP定义状态dp[i][S]dp[i][S]dp[i][S]表示的含义是前iii行满足条件，并且第i" role="presentation" style="position: relative;">iii行的状态为SSS，可行的方案数。然后状态转移:dp[i+1][nS]=#x2211;nS#x4E0E;pS=0#x4E14;nS#x53EF;#x884C;dp[i][pS]" role="presentation" style="position: relative;">dp[i+1][nS]=∑nS与pS=0且nS可行dp[i][pS]dp[i+1][nS]=∑nS与pS=0且nS可行dp[i][pS]dp[i+1][nS] = \sum_{nS与pS=0 且 nS可行 }{dp[i][pS]}
代码
#include iostream
#include cstdio
#include algorithm
using namespace std;
const int maxs 100000;
const int mod 1e8;
int state[maxs];
int cnt 0;
int dp[13][maxs];
int bks[13];
int n,m;
int main(){cinmn;for(int i 1;i m;i){for(int j 0;j n;j){int t;cint;if(t 0) bks[i] | (1j);}}for(int i 0;i (1n);i){if(i(i1)) continue;else state[cnt] i;}dp[0][0] 1; int ans 0;for(int i 1;i m;i){for(int j 0;j cnt;j){int nS state[j];if(nS bks[i]) continue;for(int k 0;k cnt;k){int pS state[k];if(pS nS) continue;dp[i][nS] dp[i-1][pS];dp[i][nS] % mod;} if(i m) ans (ans dp[i][nS])%mod;}}coutansendl;
}
P1850 换教室
题解
有关概率期望的dp但也不是很难却花了我很长时间原因是初值条件没搞清楚。
定义状态
dp[i][j][0]dp[i][j][0]dp[i][j][0]表示前iii个课程，换了j" role="presentation" style="position: relative;">jjj个且第iii个没有换，期望值的最小值。dp[i][j][1]" role="presentation" style="position: relative;">dp[i][j][1]dp[i][j][1]dp[i][j][1]表示前iii个课程，换了j" role="presentation" style="position: relative;">jjj个且第iii个申请换了，期望值的最小值。状态转移方程dp[i][j][0]" role="presentation" style="position: relative;">dp[i][j][0]dp[i][j][0]dp[i][j][0]的转移方程
由于第iii个课程没有换教室，所以教室是a[i]" role="presentation" style="position: relative;">a[i]a[i]a[i]的概率是1.01.01.0 。
当前i−1i−1i-1没有换的时候第i−1i−1i-1课程是教室a[i−1]a[i−1]a[i-1]的概率为1.01.01.0转移过来的数值是(dp[i−1][j][0]mincost(a[i−1],a[i])∗1.0∗1.0(dp[i−1][j][0]mincost(a[i−1],a[i])∗1.0∗1.0(dp[i-1][j][0] + mincost(a[i-1],a[i])*1.0*1.0当前i−1i−1i-1换了的时候如果换成功了第i−1i−1i-1课程是教室b[i−1]b[i−1]b[i-1]的概率为1.01.01.0转移过来的数值是(dp[i−1][j][1]mincost(b[i−1],a[i])∗p[i−1]∗1.0(dp[i−1][j][1]mincost(b[i−1],a[i])∗p[i−1]∗1.0(dp[i-1][j][1] + mincost(b[i-1],a[i])*p[i-1]*1.0当前i−1i−1i-1换了的时候如果换失败了第i−1i−1i-1课程是教室b[i−1]b[i−1]b[i-1]的概率为1.01.01.0转移过来的数值是(dp[i−1][j][1]mincost(a[i−1],a[i])∗(1−p[i−1])∗1.0(dp[i−1][j][1]mincost(a[i−1],a[i])∗(1−p[i−1])∗1.0(dp[i-1][j][1] + mincost(a[i-1],a[i])*(1-p[i-1])*1.0
dp[i][j][1]dp[i][j][1]dp[i][j][1]的转移方程
由于第iii个课程申请换教室了，成功的概率是p[i]" role="presentation" style="position: relative;">p[i]p[i]p[i]失败的概率是1−p[i]1−p[i]1-p[i]。
i−1i−1i-1不申请换教室。 转移过来的数值为(dp[i−1][j−1][0]G(a[i−1],b[i]))∗p[i](dp[i−1][j−1][0]G(a[i−1],a[i]))∗(1−p[i])(dp[i−1][j−1][0]G(a[i−1],b[i]))∗p[i](dp[i−1][j−1][0]G(a[i−1],a[i]))∗(1−p[i])(dp[i-1][j-1][0]+G(a[i-1],b[i]))*p[i]+(dp[i-1][j-1][0]+G(a[i-1],a[i]))*(1-p[i])
剩下的3种情况看我代码里写的吧懒得去写了。
代码
#include iostream
#include cstdio
using namespace std;
double dp[2][2007][2];
int G[307][307];
int n,m,v,e;
int a[2007],b[2007];
double p[2007];
int main(){cinnmve;for(int i 0;i n;i){scanf( %d,a[i]);}for(int i 0;i n;i){scanf( %d,b[i]);}for(int i 0;i n;i){scanf( %lf,p[i]);}for(int i 1;i v;i){for(int j 1;j v;j){if(i j) continue;G[i][j] G[j][i] 1e8;}}for(int i 0;i e;i){int u,v,t;scanf( %d %d %d,u,v,t);G[v][u] G[u][v] min(t,G[v][u]);}for(int k 1;k v;k)for(int i 1;i v;i){for(int j 1;j v;j){G[i][j] min(G[i][j],G[i][k] G[k][j]);}}for(int i 0;i 2007;i){dp[0][i][0] dp[0][i][1] dp[1][i][0] dp[1][i][1] 1e18;}dp[0][0][0] 0;//dp[0][0][1] 0;//dp[0][1][0] 0;dp[0][1][1] 0;for(int i 1;i n;i){for(int j 0;j min(m,i1);j){dp[i1][j][0] (dp[(i-1)1][j][0]G[a[i-1]][a[i]]);if(j 0) continue;dp[i1][j][0] min(dp[i1][j][0],(dp[(i-1)1][j][1]G[b[i-1]][a[i]])*p[i-1](dp[(i-1)1][j][1]G[a[i-1]][a[i]])*(1-p[i-1]));dp[i1][j][1] (dp[(i-1)1][j-1][0]G[a[i-1]][b[i]])*p[i](dp[(i-1)1][j-1][0]G[a[i-1]][a[i]])*(1-p[i]);if(j 1) continue;dp[i1][j][1] min(dp[i1][j][1],dp[(i-1)1][j-1][1]G[b[i-1]][b[i]]*p[i-1]*p[i]G[a[i-1]][b[i]]*(1-p[i-1])*p[i]G[b[i-1]][a[i]]*(p[i-1])*(1-p[i])G[a[i-1]][a[i]]*(1-p[i-1])*(1-p[i]));}}double ans 1e18;for(int i 0;i min(m,n);i){ans min(ans,dp[(n-1)1][i][0]);ans min(ans,dp[(n-1)1][i][1]);}printf(%.2lf\n,ans);
}P2831 愤怒的小鸟
题解
比较经典的动态规划问题。
由于一条抛物线至少经过1个点。我们构造nnn条抛物线，分别经过这n" role="presentation" style="position: relative;">nnn个点每条线都只能覆盖111只猪。然后我们知道除了(0,0)" role="presentation" style="position: relative;">(0,0)(0,0)(0,0)点剩下再有222个点就可以确定一条抛物线了。
我们n2" role="presentation" style="position: relative;">n2n2n^2地枚举两两点的组合生成对应的抛物线这样的话最差情况下所需的不会超过n2n2n^2条抛物线。 我们把当前构造出来的每条抛物线把这条抛物线能经过的所有点压缩成为一个状态。 问题就转变成了状态压缩dp。
定义状态dp[S]dp[S]dp[S]表示覆盖SSS状态的点，最小需要多少条抛物线。状态转移方程：
dp[S|state[i]]=min(dp[S|state[i]],dp[S]+1)" role="presentation" style="position: relative;">dp[S|state[i]]=min(dp[S|state[i]],dp[S]+1)dp[S|state[i]]=min(dp[S|state[i]],dp[S]+1)dp[S|state[i]] = min(dp[S|state[i]],dp[S]+1) 其中state[i]state[i]state[i]表示第IIscript typemath/tex idMathJax-Element-53I/script条抛物线所能经历的点集状态。
代码
#include iostream
#include cstring
#include cstdio
#define pr(x) cout#x:xendl
using namespace std;
int dp[119];
int n,m;
long double a[400],b[400];
int cover[400];
int cnt;
long double x[40],y[20];
inline long double fabs(long double x) {return x 0 ? x:-x;}
long double eps 0.000000001;
int main(){int T;cinT;while(T--){cinnm;cnt 0;memset(dp,0x3f,sizeof(dp));for(int i 0;i n;i)cinx[i]y[i];for(int i 0;i n;i){for(int j i1;j n;j){if(i j) continue;if(fabs(x[i]-x[j]) eps) {continue;}else{a[cnt] (x[i]*y[j]-x[j]*y[i])/(x[j]*x[i]*(x[j]-x[i]));b[cnt] (y[i] - a[cnt]*x[i]*x[i])/x[i];if(a[cnt] 0 || fabs(a[cnt]) eps) continue;else cnt;}}}dp[0] 0;for(int i 0;i cnt;i){int c 0;for(int j 0;j n;j){long double f a[i]*x[j]*x[j] b[i]*x[j];if(fabs(f - y[j]) eps) c | 1j;}cover[i] c;}for(int i 0;i n;i){cover[cnt] 1i;}for(int S 0;S (1n);S){for(int j 0;j cnt;j){dp[S|cover[j]] min(dp[S|cover[j]],dp[S] 1);}}coutdp[(1n)-1]endl;}return 0;
}
P1131 时态同步
题解
这是一道树形dp。
这道题的含义相当于给边添加最小的数使得从根节点道每个叶子节点路径长度都相同。
直接进行dfs回溯的时候保证子树满足题设条件(从根节点道每个叶子节点路径长度都相同)。
代码
// luogu-judger-enable-o2
#include iostream
#include cstdio
#include vector
using namespace std;
const int maxn 500007;
typedef pairint,int pii;
vectorpii G[maxn];
int n,root;
long long ans 0;
int dfs(int u,int fa){vectorint tv;int mx 0;for(auto p : G[u]){int v p.first;int c p.second;if(v fa) continue;int res dfs(v,u)c;tv.push_back(res);mx max(mx,res);}for(auto v : tv){ans mx - v;}return mx;
}
int main(){scanf(%d %d,n,root);for(int i 0;i n-1;i){int u,v,c;scanf(%d%d%d,u,v,c);G[u].push_back(make_pair(v,c));G[v].push_back(make_pair(u,c));}dfs(root,0);coutansendl;
}
后记
这几道题目都是比较经典的题目就是太老了下次应该做一些新的题这样才能跟上时代潮流呀。
