【Solution】
接上一篇,在處理有向無環圖的最長鏈問題的時候,可以在做拓撲排序的同時,一邊做DP;
設f[i]表示第i個方塊作為最上面的最高值;
f[y]=max(f[y],f[x]+h[y]);(x?>y)∈E
這樣可以保證,按階段進行DP,每次在獲取f[x]的時候,你可以保證f[x]已經獲得了;
最后取max(f[1..n])
【Code】
#include <bits/stdc++.h>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define LL long long
#define rep1(i,a,b) for (int i = a;i <= b;i++)
#define rep2(i,a,b) for (int i = a;i >= b;i--)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define ms(x,y) memset(x,y,sizeof x)
#define Open() freopen("D:\\rush.txt","r",stdin)
#define Close() ios::sync_with_stdio(0)typedef pair<
int,
int> pii;
typedef pair<LL,LL> pll;
const int dx[
9] = {
0,
1,-
1,
0,
0,-
1,-
1,
1,
1};
const int dy[
9] = {
0,
0,
0,-
1,
1,-
1,
1,-
1,
1};
const double pi =
acos(-
1.0);
const int N =
30;
struct abc{LL c,k,g;
};
int n,b[
4],nn,du[N*
3+
100];
LL dp[N*
3+
100];
abc a[N*
3+
100];
vector <int> G[N*
3+
100];
queue <int> dl;
int main()
{
int kk =
0;
while (~
scanf(
"%d",&n) && n){kk++;ms(dp,-
1);nn =
0;ms(du,
0);rep1(i,
1,N*
3) G[i].clear();rep1(i,
1,n){rep1(j,
1,
3)
scanf(
"%d",&b[j]);sort(b+
1,b+
1+
3);rep1(j,
1,
3){nn++;rep2(k,
3,
1)
if (k!=j){a[nn].c = b[k];
break;}rep1(k,
1,
3)
if (k!=j){a[nn].k = b[k];
break;}a[nn].g = b[j];}}n = nn;rep1(i,
1,n)rep1(j,
1,n)
if (a[i].c > a[j].c && a[i].k > a[j].k){G[i].pb(j);du[j]++;}
while (!dl.empty()) dl.pop();rep1(i,
1,n)
if (du[i]==
0){dl.push(i);dp[i] = a[i].g;du[i] = -
1;}
while (!dl.empty()){
int x = dl.front();dl.pop();
int len = G[x].size();rep1(i,
0,len-
1){
int y = G[x][i];
if (dp[y]==-
1){dp[y] = dp[x] + a[y].g;}
elsedp[y] = max(dp[y],dp[x]+a[y].g);du[y]--;
if (du[y]==
0){dl.push(y);du[y]= -
1;}}}LL d =
0;rep1(i,
1,n)d = max(d,dp[i]);
printf(
"Case %d: maximum height = ",kk);
printf(
"%lld\n",d);}
return 0;
}
轉載于:https://www.cnblogs.com/AWCXV/p/7626211.html
總結
以上是生活随笔為你收集整理的【UVA 437】The Tower of Babylon(拓扑排序+DP,做法)的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
