企业官网建设流程全解析

LGP4362 [NOI2002] 贪吃的九头龙

原题链接：[NOI2002] 贪吃的九头龙

分析

从某些角度而言，这个和那个没有上司的舞会其实挺像的。
居然还允许O ( n 2 ) O(n^2)O(n2)甚至O ( n 3 ) O(n^3)O(n3)！！！这不起飞了😄
那你直接设一个d p u , i dp_{u,i}dpu,i​表示以u uu为根的子树内，u uu被i ii吃掉的“难受值”的最小值。转移直接枚举，然后，以m x mxmx为根，直接输出……也不对，还要控制每个人吃的个数……坏了，这个不好做😭
难道我再记录一维？好的，看起来有做完的风险了。
别急，竟然只限制了大头吗？那，我们重新设状态，即：设d p i , j , 0 / 1 dp_{i,j,0/1}dpi,j,0/1​表示i ii子树内，大头吃了j jj个果子，i ii果子没有/吃了的“难受值”的最小值。
记录第三维的目的就是保证最大的果子吃了。转移显然。

正解

#include<bits/stdc++.h>usingnamespacestd;constintN=305;intn,m,k;intdp[N][N][2];intf[N][2];vector<pair<int,int>>e[N];intsz[N],de[N];voiddfs(intu,intfa){sz[u]=1;for(autotmp:e[u]){if(tmp.first==fa)continue;dfs(tmp.first,u);sz[u]+=sz[tmp.first];}}voiddfs_dp(intu,intfa){dp[u][0][0]=dp[u][1][1]=0;for(autotmp:e[u]){if(tmp.first==fa)continue;dfs_dp(tmp.first,u);memcpy(f,dp[u],sizeof(dp[u]));memset(dp[u],0x3f,sizeof(dp[u]));for(inti=0;i<=k;i++){for(intj=0;j<=i;j++){dp[u][i][0]=min({dp[u][i][0],dp[tmp.first][j][0]+f[i-j][0]+(m==2)*tmp.second,dp[tmp.first][j][1]+f[i-j][0]});dp[u][i][1]=min({dp[u][i][1],dp[tmp.first][j][1]+f[i-j][1]+tmp.second,dp[tmp.first][j][0]+f[i-j][1]});}}}}signedmain(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);memset(dp,0x3f,sizeof(dp));cin>>n>>m>>k;for(inti=1,a,b,c;i<n;i++){cin>>a>>b>>c;e[a].push_back({b,c});e[b].push_back({a,c});}if(n-k<m-1){cout<<-1;return0;}dfs(1,0);dfs_dp(1,0);cout<<dp[1][k][1];}

LGP1792 [国家集训队] 种树

原题链接：[国家集训队] 种树

分析

这个真的不是……哦，难道是按照相邻的和以及本身……不是哥们，那我直接DP不是也能行吗？
按照之前的贪心策略，那这个不是天然的反悔贪心吗？那个双向链表做一下就结束了。

正解

#include<bits/stdc++.h>usingnamespacestd;constintN=200005;intn,m;boolvis[N];structnode{intl,r,val;}li[N];structnode2{intval,id;booloperator<(constnode2 k)const{returnval<k.val;}};priority_queue<node2>q;voiddel(intp){li[p].l=li[li[p].l].l;li[p].r=li[li[p].r].r;li[li[p].l].r=p;li[li[p].r].l=p;}signedmain(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n>>m;if(n<m*2){cout<<"Error!";return0;}for(inti=1;i<=n;i++){cin>>li[i].val;li[i].l=i-1;li[i].r=i+1;q.push({li[i].val,i});}li[1].l=n;li[n].r=1;intans=0;for(inti=1;i<=m;i++){while(vis[q.top().id])q.pop();node2 tmp=q.top();q.pop();ans+=tmp.val;vis[li[tmp.id].l]=vis[li[tmp.id].r]=true;li[tmp.id].val=li[li[tmp.id].l].val+li[li[tmp.id].r].val-li[tmp.id].val;q.push({li[tmp.id].val,tmp.id});del(tmp.id);}cout<<ans;}