DAG上的动态规划
分析：因为时间是单向流逝的，是天然的"序"，所以影响决策的只有当前时间和所处的决策。dp[i][j]，表示在第i分钟时，处于第j个车站，最少还需要多少等待时间，因此其等待时间就有站原地等待，乘坐从左到右的车，乘坐从右到左的车，三个状态来决定。
1 #include "iostream" 2 #include "cstdio" 3 #include "cstring" 4 #include "string" 5 using namespace std; 6 const int maxn=1000+100; 7 const int maxm=10000+100; 8 const int INF=1<<30; 9 int n,T,m1,m2; 10 int t[maxn],d[maxn],e[maxn]; 11 int dp[maxm][60],vis[maxm][60][3]; 12 int main() 13 { 14 int cas=0; 15 while(cin>>n) 16 { 17 if(n==0) break; 18 cin>>T; 19 memset(vis,0,sizeof(vis)); 20 memset(dp,0,sizeof(dp)); 21 memset(t,0,sizeof(t)); 22 for(int i=1;i<n;i++) 23 cin>>t[i]; 24 cin>>m1; 25 for(int i=1;i<=m1;i++) 26 cin>>d[i]; 27 cin>>m2; 28 for(int i=1;i<=m2;i++) 29 cin>>e[i]; 30 //从左到右 31 for(int i=1;i<=m1;i++){ 32 int cnt=d[i]; 33 for(int j=1;j<=n;j++){ 34 vis[cnt][j][0]=1; 35 cnt+=t[j]; 36 } 37 } 38 //从右到左 39 for(int i=1;i<=m2;i++){ 40 int res=e[i]; 41 for(int j=n;j>=1;j--){ 42 vis[res][j][1]=1; 43 res+=t[j-1]; 44 } 45 } 46 47 for(int i=1;i<n;i++) dp[T][i]=INF; 48 dp[T][n]=0; 49 for(int i=T-1;i>=0;i--){ 50 for(int j=1;j<=n;j++){ 51 dp[i][j]=dp[i+1][j]+1; 52 if(j<n&&vis[i][j][0]&&(i+t[j]<=T)) //从左到右 53 dp[i][j]=min(dp[i][j],dp[i+t[j]][j+1]); 54 if(j>1&&vis[i][j][1]&&(i+t[j-1]<=T)) 55 dp[i][j]=min(dp[i][j],dp[i+t[j-1]][j-1]); 56 } 57 } 58 printf("Case Number %d: ",++cas); 59 if(dp[0][1]>=INF) cout<<"impossible"<<endl; 60 else cout<<dp[0][1]<<endl; 61 62 } 63 return 0; 64 }
分析：如果j能够放在i上面，从i向j连边，最后求最大高度，dfs(i)表示从第i个开始的最长距离，注意处理三个长方体三个不同面的技巧
1 #include "iostream" 2 #include "cstdio" 3 #include "cstring" 4 #include "string" 5 using namespace std; 6 const int maxn=100; 7 int n; 8 struct Node{ 9 int x,y,z; 10 }; 11 Node p[maxn]; 12 int g[maxn][maxn]; 13 bool judge(int a,int b){ 14 if((min(p[a].x,p[a].y)>min(p[b].x,p[b].y))&&(max(p[a].x,p[a].y)>max(p[b].x,p[b].y))) 15 return true; 16 return false; 17 } 18 int dp[maxn]; 19 int dfs(int i){ 20 int& ans=dp[i]; 21 if(ans!=-1) return ans; 22 ans=p[i].z; 23 for(int j=1;j<=n;j++){ 24 if(g[i][j]) 25 ans=max(ans,dfs(j)+p[i].z); 26 } 27 return ans; 28 } 29 int main() 30 { 31 //freopen("a.txt","r",stdin); 32 //freopen("a.out","w",stdout); 33 int cas=0; 34 while(cin>>n) 35 { 36 if(n==0) break; 37 for(int i=1;i<=n;i++){ 38 cin>>p[i].x>>p[i].y>>p[i].z; 39 p[i+n].x=p[i].y,p[i+n].y=p[i].z,p[i+n].z=p[i].x; 40 p[i+2*n].x=p[i].z,p[i+2*n].y=p[i].x,p[i+2*n].z=p[i].y; 41 } 42 n*=3; 43 memset(g,0,sizeof(g)); 44 for(int i=1;i<=n;i++){ 45 for(int j=1;j<=n;j++){ 46 if(judge(i,j)) 47 g[i][j]=1; 48 } 49 } 50 memset(dp,-1,sizeof(dp)); 51 int ans=0; 52 for(int i=1;i<=n;i++){ 53 ans=max(ans,dfs(i)); 54 } 55 printf("Case %d: maximum height = ",++cas); 56 cout<<ans<<endl; 57 } 58 }