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果子没有/吃了的“难受值”的最小值。记录第三维的目的就是保证最大的果子吃了。转移显然。正解#includebits/stdc.husingnamespacestd;constintN305;intn,m,k;intdp[N][N][2];intf[N][2];vectorpairint,inte[N];intsz[N],de[N];voiddfs(intu,intfa){sz[u]1;for(autotmp:e[u]){if(tmp.firstfa)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.firstfa)continue;dfs_dp(tmp.first,u);memcpy(f,dp[u],sizeof(dp[u]));memset(dp[u],0x3f,sizeof(dp[u]));for(inti0;ik;i){for(intj0;ji;j){dp[u][i][0]min({dp[u][i][0],dp[tmp.first][j][0]f[i-j][0](m2)*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));cinnmk;for(inti1,a,b,c;in;i){cinabc;e[a].push_back({b,c});e[b].push_back({a,c});}if(n-km-1){cout-1;return0;}dfs(1,0);dfs_dp(1,0);coutdp[1][k][1];}LGP1792 [国家集训队] 种树原题链接[国家集训队] 种树分析这个真的不是……哦难道是按照相邻的和以及本身……不是哥们那我直接DP不是也能行吗按照之前的贪心策略那这个不是天然的反悔贪心吗那个双向链表做一下就结束了。正解#includebits/stdc.husingnamespacestd;constintN200005;intn,m;boolvis[N];structnode{intl,r,val;}li[N];structnode2{intval,id;booloperator(constnode2 k)const{returnvalk.val;}};priority_queuenode2q;voiddel(intp){li[p].lli[li[p].l].l;li[p].rli[li[p].r].r;li[li[p].l].rp;li[li[p].r].lp;}signedmain(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cinnm;if(nm*2){coutError!;return0;}for(inti1;in;i){cinli[i].val;li[i].li-1;li[i].ri1;q.push({li[i].val,i});}li[1].ln;li[n].r1;intans0;for(inti1;im;i){while(vis[q.top().id])q.pop();node2 tmpq.top();q.pop();anstmp.val;vis[li[tmp.id].l]vis[li[tmp.id].r]true;li[tmp.id].valli[li[tmp.id].l].valli[li[tmp.id].r].val-li[tmp.id].val;q.push({li[tmp.id].val,tmp.id});del(tmp.id);}coutans;}