杯子

Kronican

【題目描述】
重慶八中在80周年校慶的時候獲捐n個杯子， 每個杯子有兩個屬性：一個是已裝水量 ai，一個是可裝水量 bi（ai <= bi）。
從一個杯子向另一個杯子倒 x 單位體積的水需要花費的時間是 x 秒。 現在用 n 個杯子中的 k 個來裝所有的水， 求最小的 k， 以及最少花費的時間 t。

輸入格式
第一行：一個正整數n（1 <= n <= 100）,代表杯子的個數。
第二行：n個正整數，a1, a2, a3, a4 , … an（1 <= ai <= 100）, ai表示第i 個杯子已裝水量。
第三行：n個正整數，b1, b2, b3, b4 , … bn（1 <= bi <= 100）,bi表示第i個杯子可裝水量。
保證對于任意一個杯子，ai <= bi
輸出格式
兩個正整數，k 和 t，分別代表最少的杯子個數和最少花費的時間。

樣例
樣例1輸入
4
3 3 4 3
4 7 6 5
樣例1輸出
2 6
樣例2輸入
2
1 1
100 100
樣例2輸出
1 1
樣例3輸入
5
10 30 5 6 24
10 41 7 8 24
樣例3輸出
3 11
數據范圍與提示
在第一個樣例中，可以把水從第1瓶倒到第2瓶。需要3秒鐘，之后，第2瓶將含有 3 + 3 = 6 單位的水。然后可以把水從第4瓶倒進第2瓶，再倒進第3瓶：倒1個單位的水在第2瓶，倒2個單位的水在第3瓶，需要 1 + 2 = 3 秒 ，所以，所有水都會裝在2個瓶子中，會花掉 3 + 3 = 6 秒來完成這件事情。

【思路+正解】

思考1：首先剛開始拿到這個題 我就聯想到Day3的也是一道杯子題，用的是狀壓DP，那可把我激動地拿起一把大刀就往前沖，再一看n的范圍 我的媽啊2^100是在搞笑嗎？ 立即pass狀壓DP

思考2：接著又看見求最小的k最少的t，min or max 腦子里的漿糊快速燃燒–>貪心！
貪心一般是只維護一個，而這里有兩個未知。啊，貪心再見，啊，貪心再見吧再見吧再見吧

思考3：那最近學的尺取？別白日做夢了騷年 有可能最優的方案是第二個和第三個杯子都滿足k條件，但是第三個杯子的水多，這個時候第一個和第二個組合明顯是更優的，pass

Finally
那么這狗時候你就憑你那馳騁坑底的經驗，貪心一般都跟DP掛鉤，既然不是狀壓DP，那就仔細尋找吧！但是又轉念一想，平時練習都是先打暴搜，然后剪枝，接著記憶化，最后DP就善良登場了 blingling~~

我們先來解決一下k杯子的問題，顯而易見，杯子的容量越大，可裝的水就越多，在總水量一定時，我們可以sort杯子容量從大到小用一個for循環找到k的最小值

搜索

仙女的搜索還是頗有造詣的 不會做的題全都暴搜偏分（小聲逼逼）
1.首先肯定有搜索的杯子編號i，選了幾個杯子tot裝水，選的杯子的總容量rest，選的所有杯子本來有的水的總和used （維護t）
2.肯定每個杯子有兩種情況，要么被選，要么不選，時間復雜度就是（2^n）完爆啊！！
3.開始剪枝吧！既然我們可以開始就得到最小的s，那么這就可以成為一個剪枝條件–當所選杯子tot > k就可以return；到此就是45的暴力代碼了；
核心代碼如下

void dfs ( int x, int used, int resr, int tot ) {if ( x > n ) return;if ( tot > k ) return;if ( tot == k && used >= sum ) //sum是n個杯子裝的所有水的總量result = min ( result, sum - ans );dfs ( x + 1, used, rest, tot );dfs ( x + 1, used+ cup[x + 1].a, rest+ cup[x + 1].b, tot + 1 ); }

4.為了更高的追求我們再來剪枝
思考一下為了讓t越小的話，我們的搜索的used就要越大，那么當走到第i個杯子時，選定了tot個杯子且容量一定的時候，tot個杯子的原有水的總和大于了現在搜索的used就可以直接return—80分代碼
5.因為這個鬼逼數據，有一個蜜汁優化就可以直沖100那個cs仙女也很迷啊
核心代碼如下

void dfs ( int i, int used, int all, int tot ) {cs ++;if ( cs > 20000000 ) return;if ( tot > k ) return;if ( all >= sum ) {result = max ( result, used );return;}if ( i > n ) return;if ( dp[i][tot][all] == 0 || dp[i][tot][all] < used )dp[i][tot][all] = used;elsereturn;dfs ( i + 1, used + cup[i].a, all + cup[i].b, tot + 1 );dfs ( i + 1, used, all, tot ); }

當然如果到此就水過了這道，我的良心實在會痛
真正的Ac思路應該是用DP

DP

1.我們考慮i這個杯子，要么選要么不選，兩種情況0/1，肯定是01背包問題了啊
2.挖掘到了這題所考察的知識點，馬上大腦搜索01背包板子代碼，dp[i][j]：表示循環處理到i號杯子時，可裝水量為j的實際最大裝水量 （注意區別：實際裝水量=可裝水量-選的杯子的原有總水量 這里要多加理解）
3.接下來就處理k的問題，前面說到k可以預先處理出來，那么我們就可以給這個DP多加一維k，$dp[i][j][k]$：表示處理到i號杯子時，一共選了k個杯子，可裝水量為j的實際最大裝水量 ，遞推式：$dp[i][j][k]=max(dp[i?1][j][k],dp[i?1][j?cup[i].b][k?1]+cup[i].a)$;
PS：三維好像會被卡空間 嘿嘿嘿
4.我們以前做的背包問題都可以減少一維i那么讓我們也來將這個DP減少一維

碼力有限的瞅瞅【代碼實現】

#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; #define MAXN 105 struct node {int a, b; }cup[MAXN]; int n, sum, vol, need, ans, all; int dp[MAXN * MAXN][MAXN]; bool cmp ( node x, node y ) {if ( x.b == y.b ) return x.a > y.a;else return x.b > y.b; } int main() {scanf ( "%d", &n );for ( int i = 1;i <= n;i ++ ) {scanf ( "%d", &cup[i].a );sum += cup[i].a;}for ( int i = 1;i <= n;i ++ ) {scanf ( "%d", &cup[i].b );all += cup[i].b;}sort ( cup + 1, cup + n + 1, cmp );for ( int i = 1;i <= n;i ++ ) {vol += cup[i].b;if( vol >= sum ) {need = i;break;}}memset ( dp, -0x7f, sizeof ( dp ) );dp[0][0] = 0;for ( int i = 1;i <= n;i ++ )for ( int j = all;j >= cup[i].b;j -- )for ( int k = 1;k <= need;k ++ )dp[j][k] = max ( dp[j][k], dp[j - cup[i].b][k - 1] + cup[i].a );for ( int i = sum;i <= all;i ++ ) //要從可以裝完所有水的sum開始枚舉，不能從vol開始因為有可能vol>sum反而跳過了正解ans = max ( ans, dp[i][need] );printf ( "%d %d", need, sum - ans );return 0; }

拓展Party

上面的思考1時，我們提到過也是一道杯子的題，與此類似，看看我們能不能解決？
騷年拔劍吧
題目是：Kronican

【題目描述】
Mislav有N個無限體積的杯子，每一個杯子中都有一些水。Mislav想喝掉所有的水，但他不想喝超過K杯水。Mistrav能做的就是將一個杯子中的水倒入另一個杯子中。 不幸的是，挑選哪兩個杯子進行倒水操作對Mislav來說很重要，因為并非所有的杯子都離他一樣遠。更準確地說，從i號杯子向j號杯子倒水所付出的代價為Cij。 幫助Mislav找到他需要付出的總代價的最小值。

輸入格式
第一行輸入包含整數N和K（1≤K≤N≤20）。表示水杯的總數和Mislav最多能喝多少杯。 接下來N行每行包含N個整數Cij（0≤Cij≤1e5）。第i+1行的第j個整數表示從第i個杯子第j個杯子倒水所需要付出的代價。保證Cii等于0。
輸出格式
輸出一個整數。表示Mislav需要付出的總代價的最小值。

樣例
樣例輸入1
3 3
0 1 1
1 0 1
1 1 0
樣例輸出1
0
樣例輸入2
3 2
0 1 1
1 0 1
1 1 0
樣例輸出2
1
樣例輸入3
5 2
0 5 4 3 2
7 0 4 4 4
3 3 0 1 2
4 3 1 0 5
4 5 5 5 0
樣例輸出3
5
數據范圍與提示：對于40%的數據，N≤10。

【正解】

拿到這道題，我想過建圖連邊，但是每兩個就有一條顯然不是，pass
貪心？也沒有通向使用的貪心。那么dp？有點像，杯子最多有20個，數據這么小。woo狀壓dp嘛！歐拉歐拉！但是考試的時候我碼不動狀壓，當時給我崩潰了orz，就只能含淚打個暴力騙騙小分，哼唧唧！

好了，為什么看得出是狀壓dp
首先n<=20就會想到狀壓或者搜索
又考慮到一杯水倒入其它杯后就不會有水倒入，顯然是個0/1狀態
因此設dp[s]為狀態為s耗費的最小步數

倒水都是從一個有水的杯子到另一個有水的杯子
如果從有水到沒水 那就做了無用功
把接受水的那個杯子里的水倒出去是沒有用的
所以每次轉移都枚舉兩個有水且不相同的兩個杯子 進行倒水即可
定義0表示有水，1表示沒有水

轉移方程：$dp[s+(1<<i)]=mindp[s]+c[i][j]$
復雜度$O(n^2?2^n)$不會炸放心搞

【代碼實現】

#include <cstdio> #include <cstring> #include <iostream> using namespace std; #define MAXN 21 int n, k; int c[MAXN][MAXN]; int dp[1 << MAXN]; //這是個好玩意兒！可以算出s的2進制的表示中有多少個1 int cup ( int s ) { int cnt = 0;while ( s ) {s &= ( s - 1 );cnt ++;}return cnt; }int main() {scanf ( "%d %d", &n, &k );for ( int i = 0;i < n;i ++ )for ( int j = 0;j < n;j ++ )scanf ( "%d", &c[i][j] );if ( n == k ) {printf ( "0" );return 0;}memset ( dp, 0x7f, sizeof ( dp ) );dp[0] = 0;for ( int s = 0;s < ( 1 << n );s ++ )for ( int i = 0;i <= n;i ++ )if ( ! ( s & ( 1 << i ) ) )for ( int j = 0;j < n;j ++ )if ( ! ( s & ( 1 << j ) ) && i != j )dp[s + ( 1 << i )] = min ( dp[s + ( 1 << i)], dp[s] + c[i][j] );int result = 0x7f7f7f7f;for ( int s = 0;s < ( 1 << n );s ++ )if ( cup ( s ) >= n - k ) result = min ( result, dp[s] );printf ( "%d", result );return 0; }

【課后小料】
想寫這個博客很久了，但一直卡著，大大的狀壓dp能力簡直了，碼得自己開始懷疑人生，但是wahahaha，我還是搞定了這個垃圾玩意兒！做個社會人(☆_☆)/~~

好了，有任何疑問歡迎留言，我是個閑人，不怕麻煩，我們再見哦~~~

總結

以上是生活随笔為你收集整理的杯子 + Kronican的全部內容，希望文章能夠幫你解決所遇到的問題。

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