正題

題目鏈接:https://www.luogu.com.cn/problem/P6775

---

題目大意

$n$種原材料，第$i$個有$d_i$個，$m$道菜品都需要$k$個原料而且每道菜最多只能用兩種材料。

要求構造方案使得滿足條件。

$1\le n\le 500,n?2\le m\le 5000,1\le k\le 5000,({\sum }_{i=1}^n{d}_i)=m\times k$

---

解題思路

額去年線上賽的時候一點想法都沒有是時候輪到我來一雪前恥歷（雖然這題還是很難

首先我們注意到一個特殊的條件$n?2\le m$，看上去沒什么想法但是看一下數據范圍有$n?1=m$和$n?1\le m$兩個部分分。

先考慮$n?1=m$的，就是原料比菜品多一個，那么我們一定有$d_{min}<k$而且$d_{min}+d_{max}>k(n=2)$。

嗯所以我們每次拿最少的一個原料和最多的一個原料做一個菜那么依舊滿足$n?1=m$的條件。

然后考慮$n\le m$的情況，不難發現肯定有$d_{max}\ge k$，所以我們直接拿最多的來做一道菜那么要不$n?1,m?1$要么$m?1$變成$n?1=m$的情況。

之后是$n?2=m$的做法，這個是本題的核心難點。

在洛谷題解上看到過一個有趣的證明，我們可以把原料看成一個點，菜品所用的兩個原料看成一條邊，那么因為$m=n?2$所以這張圖一定是不連通的，那么至少會被分成兩棵樹。

發現對于樹就是$m=n?1$的情況，所以其實是相當于我們要把$m=n?2$的情況分成兩個$m=n?1$的情況。

而且因為$m=n?1$一定有解所以我們只需要考慮怎么分就好了。

相當于我們要找出一個原料集合$S$使得
$$\sum _{i\in S}{d}_i=(|S|?1)k?\sum _{i\in S}(d_i?k)=?k$$

然后直接$dp$的復雜度是$O(T{n}^{2}k)$的，加個$bitset$優化就是$O(T\frac{n^{2}k}{w})$，可以通過本題

---

code

#include<cstdio> #include<cstring> #include<algorithm> #include<vector> #include<bitset> using namespace std; const int N=510,S=5e6+10,W=2500000; struct node{int w,id; }d[N]; struct cnode{int a,A,b,B; }v[N*10]; int T,n,m,k,tot; bool vis[N]; bitset<S>f[N]; vector<node> u; bool cmp(node x,node y) {return x.w<y.w;} void Add(int a,int A,int b=0,int B=0) {v[++tot]=(cnode){a,A,b,B};return;} void solve(int m,vector<node> &d){int n=d.size();tot=0;while(m&&m>=n){sort(d.begin(),d.end(),cmp);Add(d[n-1].id,k);d[n-1].w-=k;m--;if(!d[n-1].w)d.pop_back(),n--;}if(m==n-1){while(m){sort(d.begin(),d.end(),cmp);swap(d[0],d[n-1]);Add(d[n-1].id,d[n-1].w,d[0].id,k-d[n-1].w);d[0].w-=k-d[n-1].w;d.pop_back();n--;m--;if(!d[0].w)swap(d[0],d[n-1]),d.pop_back(),n--;}}for(int i=1;i<=tot;i++){if(v[i].b)printf("%d %d %d %d\n",v[i].a,v[i].A,v[i].b,v[i].B);else printf("%d %d\n",v[i].a,v[i].A);}u.clear();return; } int main() {scanf("%d",&T);f[0][W]=1;while(T--){scanf("%d%d%d",&n,&m,&k);for(int i=1;i<=n;i++)scanf("%d",&d[i].w),d[i].id=i;if(m==n-2){for(int i=1;i<=n;i++){int tmp=d[i].w-k;if(tmp>=0){f[i]=f[i-1];f[i]|=(f[i-1]<<tmp);}else{f[i]=f[i-1];f[i]|=(f[i-1]>>(-tmp));}}if(!f[n][W-k])puts("-1");else{memset(vis,0,sizeof(vis));for(int i=n,z=W-k;i>=1;i--){int tmp=d[i].w-k;if(f[i-1][z-tmp])u.push_back(d[i]),vis[i]=1,z-=tmp;}solve(u.size()-1,u);for(int i=1;i<=n;i++)if(!vis[i])u.push_back(d[i]);solve(u.size()-1,u);}}else{for(int i=1;i<=n;i++)u.push_back(d[i]);solve(m,u);}}return 0; }

總結

以上是生活随笔為你收集整理的P6775-[NOI2020]制作菜品【贪心,dp】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。