Too Rich

Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 1410    Accepted Submission(s): 362

• 首先由於p的數值範圍的緣故排除用完全背包來解
• 用dfs枚舉紙幣張數爆搜肯定會tle
• 所以往貪心的思想考慮
• 朴素的想法是對於p從小面額的湊到大面額的紙幣
• 但是這道題中紙幣的面額如果以倍數為關係建圖可以發現（20,50）和（200,500）會分別從10和100的節點分叉，但是其他節點均可表示比當前節點大的所有面額的紙幣
• 這個特性意味著用小面額20或200有湊不出50和500以及其奇數倍數值的情況
• 反思之前提到的朴素的貪心想法
• 如果湊到最後出現湊的數額不等於p
• 則一定是最後加的當前最大面額導致的
• 補救的辦法應是用之前使用的小面額紙幣湊當前導致超範圍的紙幣的面額
• 那麼如之前所述
• 10種紙幣的面額不是一種很好的結構
• 不能保證小面額紙幣一定可以湊成任意大面額紙幣
• 就存在不可補救的情況存在
• 而且我們沒法保證當前湊數的結果是正確的湊數結果
• 那有沒有補救的辦法呢？
• 還是有滴呀
• 只要把紙幣面額更改成最優結構即可
• 就是每次使用兩張50或500，就把這種面額的紙幣算是取消了
• 之後就剩下8種面額的紙幣，而且都滿足可以湊成任意比當前面額大的紙幣的條件
• 剩下的就是討論50和500兩種紙幣使用張數奇偶性的問題了
• 4種情況，在貪心前加上就行
• 高中數學老師講得好啊！“正難則反”
• 這個題就可以反向思維，只要湊出紙幣剩餘面額的最小張數，減一下就是結果啊！
• 如果正向考慮，應該是貪心湊數，最後對於多出來的數值用小面額先代替大面額之後打補丁
• 好吧，很麻煩
• 但是反向來做，不用代替和打補丁，就是直接用最大面值來湊，不存在打補丁的問題

 1 #include <iostream>
 2 #include <string>
 3 #include <cstdio>
 4 #include <cstring>
 5 #include <algorithm>
 6 #include <climits>
 7 #include <cmath>
 8 #include <vector>
 9 #include <queue>
10 #include <stack>
11 #include <set>
12 #include <map>
13 using namespace std;
14 typedef long long           LL ;
15 typedef unsigned long long ULL ;
16 const int    maxn = 1e5 + 10   ;
17 const int    inf  = 0x3f3f3f3f ;
18 const int    npos = -1         ;
19 const int    mod  = 1e9 + 7    ;
20 const int    mxx  = 100 + 5    ;
21 const double eps  = 1e-6       ;
22 const double PI   = acos(-1.0) ;
23 
24 int c[11]={0,1,5,10,20,50,100,200,500,1000,2000};
25 int a[20], b[20], T, ans, tot;
26 LL p, sum;
27 int main(){
28     // freopen("in.txt","r",stdin);
29     // freopen("out.txt","w",stdout);
30     while(~scanf("%d",&T)){
31         while(T--){
32             sum=0;
33             tot=0;
34             ans=inf;
35             scanf("%lld",&p);
36             for(int i=1;i<11;i++){
37                 scanf("%d",&a[i]);
38                 tot+=a[i];
39                 sum+=a[i]*c[i];
40             }
41             if(sum<p){
42                 printf("-1\n");
43                 continue;
44             }
45             p=sum-p;
46             memcpy(b,a,sizeof(a));
47             for(int i=0;i<2;i++)
48                 for(int j=0;j<2;j++)
49                     if(i<=a[5] && j<=a[8]){
50                         b[5]=a[5]-i;
51                         b[8]=a[8]-j;
52                         LL t=p-i*c[5]-j*c[8];
53                         int cnt=i+j;
54                         for(int k=10;k>0&&t>0;k--){
55                             int del=min(b[k],(int)t/c[k]);
56                             if((k==5||k==8)&&(del&1))
57                                 del--;
58                             t-=del*c[k];
59                             cnt+=del;
60                         }
61                         if(t==0)
62                             ans=min(ans,cnt);
63                     }
64             if(ans==inf)
65                 ans=-1;
66             else
67                 ans=tot-ans;
68             printf("%d\n",ans);
69         }
70     }
71     return 0;
72 }