昨晚上的比赛：网站崩了，交了五发就走了
今天重判了一次，除了A都过了。。。（细节错误）迷
基于最近几场比赛非常差的表现，今天又回去重新看了三大DP。
数位DP：
主要优点在于记忆化。这类题目应该是比较好辨认的。。。（现在只会dfs写法了）
1、一段区间内满足给定条件的数的个数。这里条件的改变主要影响dfs的参数以及内部的操作。
2、求一段区间内第几个满足条件的数。这里就用到了二分。
注意：初始化写在外面可能会TLE，是否具有前导0。
求区间内第几个含666的数（数位dp+二分）：
#include<iostream> #include<cmath> #include<cstring> #include<algorithm> #include<cstdio> #include<map> using namespace std; const long long INF=0x3f3f3f3f3f3f3f3fll; long long f[30][6]; int a[30]; int n,m; int ind; long long dfs(int pos,int s,bool limit) { if(pos==-1) return s==3; if(!limit&&f[pos][s]!=-1) return f[pos][s]; int i,end=limit?a[pos]:9; long long ans=0; for(i=0; i<=end; i++) { int ns=s; if(s==2&&i==6) ns=3; else if(s==2&&i!=6) ns=0; else if(s==1&&i==6) ns=2; else if(s==1&&i!=6) ns=0; else if(s==0&&i==6) ns=1; ans+=dfs(pos-1,ns,limit&&i==end); } if(!limit) f[pos][s]=ans; return ans; } long long solve(long long xx){ int pos=0; while(xx){ a[pos++]=xx; xx/=10; } return dfs(pos-1,0,1); } long long go(long long n){ long long fir=0,end=INF; long long ans=-1; while(fir<=end){ long long mid=(fir+end)>>1; if(solve(mid)<n){ fir=mid+1; } else{ ans=mid; end=mid-1; } } return ans; } int main() { memset(f,-1,sizeof(f)); int t; long long x,y; while (scanf("%d",&t)!=EOF) { while (t--){ scanf("%lld",&x); printf("%lld\n",go(x)); } } return 0; }树形DP：
在树上dp利用dfs完成状态转移。（话说为什么忘得这么快？！赶紧去翻了自己的博客。。。虽然也很迷）
此类问题我个人还是不好辨认的。不过这类题目都是在树上进行操作，而且有状态转移，这类问题状态转移还是关键也是难点。。。
经典问题：从树上一个点出发所能达到的最远距离。求树的重心（删除该点后使最大的子树的最小）。
从树上一个点出发所能达到的最远距离：（经典）
#include<iostream> #include<cmath> #include<cstring> #include<algorithm> #include<cstdio> #include<string> #include<queue> #include<vector> #include<map> using namespace std; const int mx=10005; struct node{ int w,v,nex; }a[mx<<1]; int dp[mx][3],h[mx],n,t; void add(int w,int v,int f) { a[t].w=w; a[t].v=v; a[t].nex=h[f]; h[f]=t++; } void dfs1(int f); void dfs2(int f); int main() { while(scanf("%d",&n)!=EOF) { memset(h,-1,sizeof(h)); memset(dp,0,sizeof(dp));t=0; for(int i=2;i<=n;i++) { int x,y; scanf("%d%d",&x,&y); add(y,i,x); } dfs1(1);dfs2(1); for(int i=1;i<=n;i++)printf("%d\n",max(dp[i][2],dp[i][0])); } return 0; } void dfs1(int f) { for(int i=h[f];i!=-1;i=a[i].nex) { int z=a[i].v; dfs1(z); int w=dp[z][0]+a[i].w; if(w>=dp[f][0]) { dp[f][1]=dp[f][0]; dp[f][0]=w; } else if(w>dp[f][1]) dp[f][1]=w; } } void dfs2(int f) { for(int i=h[f];i!=-1;i=a[i].nex) { int z=a[i].v; int w=dp[z][0]+a[i].w; if(w==dp[f][0]) { dp[z][2]=max(dp[f][2],dp[f][1])+a[i].w; } else dp[z][2]=max(dp[f][2],dp[f][0])+a[i].w; dfs2(z); } }状压dp待总结。。。这几天要付出十倍的努力，全力备战省赛。
另：wf告诉我们gets不能随便用了。。。
