傳送門

我現(xiàn)在還是不明白為什么NOIPd2t3會是一道動態(tài)dp……

首先關于動態(tài)dp可以看這里

然后這里就是把把矩陣給改一改，改成這個形式\[\left[dp_{i-1,0},dp_{i-1,1}\right]\times \left[\begin{matrix}\infty&ldp_{i,1}\\ldp_{i,0}&ldp_{i,1}\end{matrix}\right]\]

然后就是改成\(longlong\)，以及改一改取最小。關于強制取或不取，只要讓值加上一個極大值或減去極大值就可以了

于是這么想著并交上去的我就調(diào)了一天

這里最主要的問題是，因為矩乘之后，第二行的兩個數(shù)才是\(dp_{i,0}\)和\(dp_{i,1}\)，然后沒發(fā)現(xiàn)這點，于是就沒有于是了……

//minamoto #include<bits/stdc++.h> #define R register #define ll long long #define mx 1e10 #define inf 1e12 #define fp(i,a,b) for(R int i=a,I=b+1;i<I;++i) #define fd(i,a,b) for(R int i=a,I=b-1;i>I;--i) #define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v) using namespace std; char buf[1<<21],*p1=buf,*p2=buf; inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;} int read(){R int res,f=1;R char ch;while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');return res*f; } inline void getstr(){char ch;while((ch=getc())<'A'||ch>'Z');while((ch=getc())>='A'&&ch<='Z');} char sr[1<<21],z[20];int C=-1,Z=0; inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;} void print(R ll x){if(C>1<<20)Ot();if(x<0)sr[++C]='-',x=-x;while(z[++Z]=x%10+48,x/=10);while(sr[++C]=z[Z],--Z);sr[++C]='\n'; } const int N=1e5+5; inline ll min(R ll x,R ll y){return x<y?x:y;} inline ll max(R ll x,R ll y){return x>y?x:y;} struct eg{int v,nx;}e[N<<1];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]!=u&&ch[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(l>r)return 0;int tot=0;fp(i,l,r)tot+=lsz[st[i]];for(int i=l,now=lsz[st[i]];i<=r;++i,now+=lsz[st[i]])if(now*2>=tot){ch[st[i]][0]=sbuild(i+1,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 p=u;p;p=son[p])vis[p]=1;for(int p=u;p;p=son[p])go(p)if(!vis[v])pd(p,build(v));top=0;for(int p=u;p;p=son[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 p=u;p;p=fa[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),n=read(),m=read(),getstr();fp(i,1,n)val[i]=read();for(R int i=1,u,v;i<n;++i)u=read(),v=read(),add(u,v),add(v,u);dfs(1,0),init(),rt=build(1);while(m--){int u=read(),x=read(),v=read(),y=read();if((u==fat[v]||v==fat[u])&&!x&&!y)print(-1);else{update(u,x),update(v,y);print(mul[rt].mn()+(x+y)*mx);update(u,x^1),update(v,y^1);}}return Ot(),0; }

轉(zhuǎn)載于:https://www.cnblogs.com/bztMinamoto/p/10192659.html

總結

以上是生活随笔為你收集整理的P5024 保卫王国的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。