济宁正德网站建设,做网站需要买服务器,网站建设年终总结,阐述网站建设的步骤【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… 【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,rt1
#define rson m1,r,rt1|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 pairint,int pii;
typedef pairLL,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*3100];
LL dp[N*3100];
abc a[N*3100];
vector int G[N*3100];
queue int dl;int main()
{//Open();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(b1,b13);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
