AcWing 677. 找零
原题链接
简单
作者:
指间理想
,
2021-05-10 19:41:17
,
所有人可见
,
阅读 2
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 50;
#define reset(x) memset(x, 0, sizeof(x))
#define Q_in_out ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
typedef long long int ll;
typedef long double ld;
typedef pair<int, int> P;
int solve()
{
int n;
cin>>n;
n=1024-n;
int a[4]={1,4,16,64};
int res[1024];
memset(res,N,sizeof(res));
res[0]=0;
for(int i=1;i<=n;i++){
for(int j=0;j<4;j++){
if(i-a[j]>=0){
res[i]=min(res[i-a[j]]+1,res[i]);
}
}
}
cout<<res[n];
return 0;
}
int main()
{
Q_in_out
int t;
// cin>>t;
t=1;
while(t--)
{
solve();
cout<<endl;
}
return 0;
}