正题
题目链接:https://www.luogu.com.cn/problem/P4026
题目大意
3
3
3个人，有一些面值为
100
,
50
,
20
,
10
,
5
,
1
100,50,20,10,5,1
100,50,20,10,5,1的钱，一些人欠一些人钱，求最少交换多少张钞票可以还清。
解题思路
我们设
f
i
,
j
,
k
f_{i,j,k}
fi,j,k表示考虑到第
i
i
i种面值，第一个人有
j
j
j元第二个人有
k
k
k元时的最小交换次数。
然后
d
p
dp
dp即可。
c
o
d
e
code
code
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std
;
const int N
=7,val
[7]={0,100,50,20,10,5,1},inf
=2147483647/3;
int sum
,a
[N
][N
],cnt
[N
],s
[N
],f
[N
][1100][1100],ans
;
int main()
{
int x1
,x2
,x3
;scanf("%d%d%d",&x1
,&x2
,&x3
);
for(int i
=1;i
<=3;i
++)
for(int j
=1;j
<=6;j
++){
scanf("%d",&a
[i
][j
]);
s
[i
]+=a
[i
][j
]*val
[j
];
sum
+=a
[i
][j
]*val
[j
];
cnt
[j
]+=a
[i
][j
];
}
memset(f
,0x3f,sizeof(f
));
f
[0][s
[1]][s
[2]]=0;
for(int i
=1;i
<=6;i
++)
for(int j
=0;j
<=sum
;j
++)
for(int k
=0;k
+j
<=sum
;k
++){
if(f
[i
-1][j
][k
]>=inf
)continue;
for(int x1
=0;x1
<=cnt
[i
];x1
++)
for(int x2
=0;x1
+x2
<=cnt
[i
];x2
++){
int now1
=j
-(a
[1][i
]-x1
)*val
[i
];
int now2
=k
-(a
[2][i
]-x2
)*val
[i
];
int x3
=cnt
[i
]-x1
-x2
;
if(now1
>=0&&now2
>=0&&now1
+now2
<=sum
)
f
[i
][now1
][now2
]=min(f
[i
][now1
][now2
],f
[i
-1][j
][k
]+(abs(x1
-a
[1][i
])+abs(x2
-a
[2][i
])+abs(x3
-a
[3][i
]))/2);
}
}
int X1
=s
[1]+x3
-x1
,X2
=s
[2]+x1
-x2
,X3
=s
[3]+x2
-x3
;ans
=inf
+10;
for(int i
=0;i
<=6;i
++)ans
=min(ans
,f
[i
][X1
][X2
]);
if(X1
<0||X2
<0||X3
<0||ans
>inf
)return printf("impossible")&0;
printf("%d",ans
);return 0;
}
