P4026题解

· · 题解

题目

传送门

分析

一道极其诡异的题目

我们千万不要被题目所迷惑，去考虑要循环地还钱。要重新理解一下怎样还钱。

第一步：ABC 三人把所有的钱掏出来，放在桌子上

第二步：AB 拿走他们应该拿走的钱，剩下的就是 C 该拿走的钱

所谓的交换代价，就是指原本的钱减去拿走的钱的绝对值。怎么理解？

假设 A 原本有 old_a 元钱，那么

old_a = 100\times a_{100}+50\times a_{50}+20\times a_{20}+10\times a_{10}+5\times a_{5}+1 \times a_{1}

其中 a_n 表示面额为 n 的纸币 A 有多少张。

设 A 应该拿走 new_a 元钱，那么

new_a=old_a-x_1+x_3

同理：

new_b=old_b-x_2+x_1 new_c=old_c-x_3+x_2

问题就转化为了：求六种货币，能够取两个集合，sum_1=new_a\ sum_2=new_b (sum-sum_1-sum_2=new_c)

好了，来玩背包吧

背包

设 f_{i,x,y} 表示考虑前 i 种货币，构造 a 拿走 x 元，b 拿走 y 元的最小交换次数

令 table_i=a_i+b_i+c_i

v_{1...6}={100,50,20,10,5,1} f_{i,x,y}=\min_{0 \leq p \leq table_i\ 0 \leq q \leq table_i-p}{f_{(i-1)(x-p \times v_i)(y-q \times v_i)}}+|p-a_i|+|q-b_i|+|num_i-p-q-c_i|

最后答案就是 f_{6,new_a,new_b}

有人说这个会 TLE ，其实是不会的，因为数组的第一维可以滚动数组滚掉。大小就是 1\times 10^{6}。就算不要滚动数组，吸个氧也过了。

代码

方程都列的这么详细了，代码还需要吗？

#include<iostream>
#include<cstring>
#include<cmath>

using namespace std;
int f[1001][1001]; 
int main()
{
  int ab, bc, ca;
  cin >> ab >> bc >> ca;
  int a[7], b[7], c[7], num[7];
  int v[] = {0,100,50,20,10,5,1};
  int Ta = 0, Tb = 0, Tc = 0; 
  for (int i = 1; i <= 6; ++i) cin >> a[i], Ta += a[i]*v[i];
  for (int i = 1; i <= 6; ++i) cin >> b[i], Tb += b[i]*v[i];
  for (int i = 1; i <= 6; ++i) cin >> c[i], Tc += c[i]*v[i];
  for (int i = 1; i <= 6; ++i) num[i] = a[i] + b[i] + c[i];
  Ta += ca - ab;
  Tb += ab - bc;
  Tc += bc - ca;
  memset(f, 0x3f, sizeof (f));
  f[0][0]= 0;
  for (int i = 1; i <= 6; ++i) {
    for (int x = Ta; x >= 0; x--)
       for (int y = Tb; y >= 0; y--)
         {
           // to calc f[i,x,y];
           for (int p = 0; p <= num[i]; ++p) if (x-p*v[i] >= 0){
             for (int q = 0; p+q <= num[i]; ++q)  if (y-q*v[i]>=0){
                int tmp = f[x-p*v[i]][y-q*v[i]] 
                        + abs(p-a[i])+abs(q-b[i])+abs(p+q-a[i]-b[i]);
                if (f[x][y] > tmp)
                  f[x][y] = tmp;
             }
            }
         } 
  }
  if(f[Ta][Tb]<1000000000) 
  cout << f[Ta][Tb] / 2;    
  else
  cout << "impossible"; 
}

望通过，谢谢