今天结合大白学了稍微进阶一点的dp，下面是我的一点个人理解，
状压dp：以前也做过几个状压dp的题目，但是都是当时看题解明白，过后就忘了，今天重新学习一遍感觉状压dp是解决一类在状态集合之间相互转移的问题的办法，整数上的dp我们可以直接记录某个状态，因为他就是一个数，而如果状态是一个集合的话我们就没办法直接记录了，这时候就需要用到状态压缩的思想，最基本的状态压缩就是用二进制来表示集合中每个元素的操作过或者未操作，还有很多状态压缩的方法有待学习。
数据结构优化dp：大白上给的例题是用线段树优化dp，个人认为能优化的原因是很多dp都会求一个区间最值（有时需要转化），而这个区间最值的求解我们就可以用各种RMQ的方法去优化了。
POJ2686代码：
#include<iostream> #include<algorithm> #include<string.h> #include<stdio.h> #define inf 0x3f3f3f3f using namespace std; int t[10],W[50][50]; double dp[33][(1<<8)+10]; int main() { int n,m,p,a,b,u,v,w; while(cin>>n>>m>>p>>a>>b&&a+b+p+n+m) { memset(W,0,sizeof(W)); memset(t,0,sizeof(t)); for(int i=0;i<n;i++) cin>>t[i]; for(int i=0;i<p;i++) { cin>>u>>v>>w; W[u][v]=W[v][u]=w; } for(int i=1;i<=m;i++) for(int j=0;j<(1<<n);j++) { dp[i][j]=inf; } dp[a][(1<<n)-1]=0; for(int j=(1<<n)-1;j>=0;j--) { for(int i=1;i<=m;i++) { for(int k=1;k<=m;k++) { if(!W[i][k])continue; for(int x=0;x<n;x++) { if(j&(1<<x)) { dp[k][j-(1<<x)]=min(dp[k][j-(1<<x)],dp[i][j]+W[i][k]*1.0/t[x]); } } } } } double ans=*min_element(dp[b],dp[b]+(1<<n)); if(ans==inf) cout<<"Impossible\n"; else printf("%.3f\n",ans); } } #include<iostream> #include<stdio.h> #include<algorithm> #include<string.h> const int inf = 0x3f3f3f3f; using namespace std; int t[10],w[33][33]; double dp[(1<<8)+10][33]; int main() { int n,m,p,a,b,u,v,c; while(cin>>n>>m>>p>>a>>b&&n+m+p+a+b) { memset(w,-1,sizeof(w)); memset(t,0,sizeof(t)); for(int i=0;i<n;i++) cin>>t[i]; while(p--) { cin>>u>>v>>c; w[u-1][v-1]=w[v-1][u-1]=c; } for(int i=0;i<1<<n;i++) fill(dp[i],dp[i]+m,inf); dp[(1<<n)-1][a-1]=0; double res=inf; for(int s=(1<<n)-1;s>=0;s--) { res=min(res,dp[s][b-1]); for(int v=0;v<m;v++) { for(int i=0;i<n;i++) { if(s>>i&1) { for(int u=0;u<m;u++) { if(w[u][v]>=0) { dp[s&~(1<<i)][u]=min(dp[s&~(1<<i)][u],dp[s][v]+w[u][v]*1.0/t[i]); } } } } } } if(res==inf) printf("Impossible\n"); else printf("%.3f\n",res); } } POJ1769代码： #include<iostream> #include<algorithm> #include<stdio.h> #include<string.h> #define lson l,mid,rt<<1 #define rson mid+1,r,rt<<1|1 #define inf 0x3f3f3f3f using namespace std; const int MAXN = 50050; int S[MAXN*10],T[MAXN*10]; int dp[MAXN],tree[MAXN<<2]; void pushup(int rt) { tree[rt]=min(tree[rt<<1],tree[rt<<1|1]); } void update(int id,int x,int l,int r,int rt) { if(l==r) { tree[rt]=x; return ; } int mid=(l+r)>>1; if(id<=mid) update(id,x,lson); else update(id,x,rson); pushup(rt); } int query(int L,int R,int l,int r,int rt) { if(L<=l&&r<=R) return tree[rt]; int mid=(l+r)>>1,ans=inf; if(L<=mid) ans=min(ans,query(L,R,lson)); if(R>mid) ans=min(ans,query(L,R,rson)); return ans; } int main() { int n,m,l,r; cin>>n>>m; memset(dp,inf,sizeof(dp)); memset(tree,inf,sizeof(tree)); dp[1]=0; update(1,0,1,n,1); while(m--) { scanf("%d%d",&l,&r); dp[r]=min(dp[r],query(l,r,1,n,1)+1); update(r,dp[r],1,n,1); } cout<<dp[n]<<endl; }
