js网站开发工具,做网站找外包好吗,wordpress 权限阅读,wordpress好还是织梦好传送门 我现在还是不明白为什么NOIPd2t3会是一道动态dp…… 首先关于动态dp可以看这里 然后这里就是把把矩阵给改一改#xff0c;改成这个形式\[\left[dp_{i-1,0},dp_{i-1,1}\right]\times \left[\begin{matrix}\inftyldp_{i,1}\\ldp_{i,0}ldp_{i,1}\end{matrix}\ri…传送门 我现在还是不明白为什么NOIPd2t3会是一道动态dp…… 首先关于动态dp可以看这里 然后这里就是把把矩阵给改一改改成这个形式\[\left[dp_{i-1,0},dp_{i-1,1}\right]\times \left[\begin{matrix}\inftyldp_{i,1}\\ldp_{i,0}ldp_{i,1}\end{matrix}\right]\] 然后就是改成\(longlong\)以及改一改取最小。关于强制取或不取只要让值加上一个极大值或减去极大值就可以了 于是这么想着并交上去的我就调了一天 这里最主要的问题是因为矩乘之后第二行的两个数才是\(dp_{i,0}\)和\(dp_{i,1}\)然后没发现这点于是就没有于是了…… //minamoto
#includebits/stdc.h
#define R register
#define ll long long
#define mx 1e10
#define inf 1e12
#define fp(i,a,b) for(R int ia,Ib1;iI;i)
#define fd(i,a,b) for(R int ia,Ib-1;iI;--i)
#define go(u) for(int ihead[u],ve[i].v;i;ie[i].nx,ve[i].v)
using namespace std;
char buf[121],*p1buf,*p2buf;
inline char getc(){return p1p2(p2(p1buf)fread(buf,1,121,stdin),p1p2)?EOF:*p1;}
int read(){R int res,f1;R char ch;while((chgetc())9||ch0)(ch-)(f-1);for(resch-0;(chgetc())0ch9;resres*10ch-0);return res*f;
}
inline void getstr(){char ch;while((chgetc())A||chZ);while((chgetc())AchZ);}
char sr[121],z[20];int C-1,Z0;
inline void Ot(){fwrite(sr,1,C1,stdout),C-1;}
void print(R ll x){if(C120)Ot();if(x0)sr[C]-,x-x;while(z[Z]x%1048,x/10);while(sr[C]z[Z],--Z);sr[C]\n;
}
const int N1e55;
inline ll min(R ll x,R ll y){return xy?x:y;}
inline ll max(R ll x,R ll y){return xy?x:y;}
struct eg{int v,nx;}e[N1];int head[N],tot;
inline void add(R int u,R int v){e[tot]{v,head[u]},head[u]tot;}
int sz[N],lsz[N],val[N],son[N],fat[N],n,m;
void dfs(int u,int fa){sz[u]1;go(u)if(v!fa){fat[v]u,dfs(v,u),sz[u]sz[v];if(sz[v]sz[son[u]])son[u]v;}lsz[u]sz[u]-sz[son[u]];
}
struct Matrix{ll a[2][2];Matrix(){a[0][0]a[0][1]a[1][0]a[1][1]inf;}Matrix(R int x){a[0][0]a[1][1]0,a[0][1]a[1][0]inf;}inline ll mn(){return min(min(a[0][0],a[0][1]),min(a[1][0],a[1][1]));}inline ll* operator [](const int x){return a[x];}Matrix operator *(Matrix b){Matrix res;res[0][0]min(a[0][0]b[0][0],a[0][1]b[1][0]);res[0][1]min(a[0][0]b[0][1],a[0][1]b[1][1]);res[1][0]min(a[1][0]b[0][0],a[1][1]b[1][0]);res[1][1]min(a[1][0]b[0][1],a[1][1]b[1][1]);return res;}
}mul[N],w[N];int ch[N][2],fa[N],st[N],top,rt;bool vis[N];
inline void upd(R int u){mul[u]mul[ch[u][0]]*w[u]*mul[ch[u][1]];}
inline void pd(R int u,R int v){w[u][0][1]mul[v].mn(),w[u][1][1]w[u][0][1],w[u][1][0]mul[v][1][1],fa[v]u;
}
inline bool is(R int u){return ch[fa[u]][0]!uch[fa[u]][1]!u;}
inline void init(){fp(i,1,n)w[i][0][1]w[i][1][1]val[i],w[i][1][0]0,mul[i]w[i];}
int sbuild(int l,int r){if(lr)return 0;int tot0;fp(i,l,r)totlsz[st[i]];for(int il,nowlsz[st[i]];ir;i,nowlsz[st[i]])if(now*2tot){ch[st[i]][0]sbuild(i1,r),ch[st[i]][1]sbuild(l,i-1);fa[ch[st[i]][0]]fa[ch[st[i]][1]]st[i],upd(st[i]);return st[i];}
}
int build(int u){for(int pu;p;pson[p])vis[p]1;for(int pu;p;pson[p])go(p)if(!vis[v])pd(p,build(v));top0;for(int pu;p;pson[p])st[top]p;return sbuild(1,top);
}
void update(int u,int vva){w[u][0][1]vva?-mx:mx,w[u][1][1]w[u][0][1];for(R int pu;p;pfa[p])if(is(p)fa[p]){w[fa[p]][0][1]-mul[p].mn(),w[fa[p]][1][1]w[fa[p]][0][1];w[fa[p]][1][0]-mul[p][1][1],upd(p);w[fa[p]][0][1]mul[p].mn(),w[fa[p]][1][1]w[fa[p]][0][1];w[fa[p]][1][0]mul[p][1][1];}else upd(p);
}
int f[N][2];
void dp(int u,int fa){f[u][0]0,f[u][1]val[u];go(u)if(v!fa){dp(v,u),f[u][0]f[v][1],f[u][1]min(f[v][0],f[v][1]);}
}
int main(){
// freopen(testdata.in,r,stdin);w[0]mul[0]Matrix(1),nread(),mread(),getstr();fp(i,1,n)val[i]read();for(R int i1,u,v;in;i)uread(),vread(),add(u,v),add(v,u);dfs(1,0),init(),rtbuild(1);while(m--){int uread(),xread(),vread(),yread();if((ufat[v]||vfat[u])!x!y)print(-1);else{update(u,x),update(v,y);print(mul[rt].mn()(xy)*mx);update(u,x^1),update(v,y^1);}}return Ot(),0;
} 转载于:https://www.cnblogs.com/bztMinamoto/p/10192659.html
