NC50532. Banknotes
描述
输入描述
第一行一个数n；
接下来一行n个整数；
第三行n个整数，表示每种硬币的个数；
最后一行一个数k，表示要凑的面值数。
输出描述
第一行一个数表示最少需要付的硬币数。
示例1
输入:
3 2 3 5 2 2 1 10
输出:
3
Java(javac 1.8) 解法, 执行用时: 196ms, 内存消耗: 31544K, 提交时间: 2021-03-04 20:31:56
import java.io.*;
import java.lang.reflect.Type;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.math.RoundingMode;
import java.text.DecimalFormat;
import java.util.*;
import java.util.concurrent.ArrayBlockingQueue;
import java.util.concurrent.Future;
import java.util.concurrent.FutureTask;
import java.util.concurrent.locks.LockSupport;
public class Main {
static class Task {
public static String roundS(double result, int scale) {
String fmt = String.format("%%.%df", scale);
return String.format(fmt, result);
// DecimalFormat df = new DecimalFormat("0.000000");
// double result = Double.parseDouble(df.format(result));
}
int rt(int x) {
if (x != fa[x]) {
int to = rt(fa[x]);
// dp[x] ^= dp[fa[x]];
fa[x] = to;
return to;
}
return x;
}
void combine(int x, int y, int val) {
int rt1 = rt(x);
int rt2 = rt(y);
if (rt1 == rt2)
return;
fa[rt1] = rt2;
// dp[rt1] = dp[x] ^ dp[y] ^ val;
g--;
}
int fa[], dp[];
int g;
static int MAXN = 10000;
static Random rd = new Random(348957438574659L);
static int[] ch[], val, size, rnd, cnt;
static int len = 0, rt = 0;
// return new node, the node below s
static int rotate(int s, int d) {
// child
int x = ch[s][d ^ 1];
// give me grandson
ch[s][d ^ 1] = ch[x][d];
// child become father
ch[x][d] = s;
// update size, update new son first
update(s);
update(x);
return x;
}
static void update(int s) {
size[s] = size[ch[s][0]] + size[ch[s][1]] + cnt[s];
}
// 0 for left, 1 for right
static int cmp(int x, int num) {
if (val[x] == num)
return -1;
return num < val[x] ? 0 : 1;
}
static int insert(int s, int num) {
if (s == 0) {
s = ++len;
val[s] = num;
size[s] = 1;
rnd[s] = rd.nextInt();
cnt[s] = 1;
} else {
int d = cmp(s, num);
if (d != -1) {
ch[s][d] = insert(ch[s][d], num);
// father's random should be greater
if (rnd[s] < rnd[ch[s][d]]) {
s = rotate(s, d ^ 1);
} else {
update(s);
}
} else {
++cnt[s];
++size[s];
}
}
return s;
}
static int del(int s, int num) {
int d = cmp(s, num);
if (d != -1) {
ch[s][d] = del(ch[s][d], num);
update(s);
} else if (ch[s][0] * ch[s][1] == 0) {
if (--cnt[s] == 0) {
s = ch[s][0] + ch[s][1];
}
} else {
int k = rnd[ch[s][0]] < rnd[ch[s][1]] ? 0 : 1;
// k points to smaller random value,then bigger one up
s = rotate(s, k);
// now the node with value num become the child
ch[s][k] = del(ch[s][k], num);
update(s);
}
return s;
}
static int getKth(int s, int k) {
int lz = size[ch[s][0]];
if (k >= lz + 1 && k <= lz + cnt[s]) {
return val[s];
} else if (k <= lz) {
return getKth(ch[s][0], k);
} else {
return getKth(ch[s][1], k - lz - cnt[s]);
}
}
static int getRank(int s, int value) {
if (s == 0)
return 1;
if (value == val[s])
return size[ch[s][0]] + 1;
if (value < val[s])
return getRank(ch[s][0], value);
return getRank(ch[s][1], value) + size[ch[s][0]] + cnt[s];
}
static int getPre(int data) {
int ans = -1;
int p = rt;
while (p > 0) {
if (data > val[p]) {
if (ans == -1 || val[p] > val[ans])
ans = p;
p = ch[p][1];
} else
p = ch[p][0];
}
return ans != -1 ? val[ans] : (-2147483647);
}
static int getNext(int data) {
int ans = -1;
int p = rt;
while (p > 0) {
if (data < val[p]) {
if (ans == -1 || val[p] < val[ans])
ans = p;
p = ch[p][0];
} else
p = ch[p][1];
}
return ans != -1 ? val[ans] : 2147483647;
}
static boolean find(int s, int num) {
while (s != 0) {
int d = cmp(s, num);
if (d == -1)
return true;
else
s = ch[s][d];
}
return false;
}
static int ans = -10000000;
static boolean findX(int s, int num) {
while (s != 0) {
if (val[s] <= num) {
ans = num;
}
int d = cmp(s, num);
if (d == -1)
return true;
else {
s = ch[s][d];
}
}
return false;
}
long gcd(long a, long b) {
if (b == 0)
return a;
return gcd(b, a % b);
}
void linear_sort(int arr[]) {
int d = 65536;
ArrayDeque bucket[] = new ArrayDeque[d];
for (int j = 0; j < d; ++j) {
bucket[j] = new ArrayDeque();
}
for (int u : arr) {
bucket[u % d].offer(u);
}
int pos = 0;
for (int j = 0; j < d; ++j) {
while (bucket[j].size() > 0) {
arr[pos++] = (int)bucket[j].pollFirst();
}
}
for (int u : arr) {
bucket[u / d].offer(u);
}
pos = 0;
for (int j = 0; j < d; ++j) {
while (bucket[j].size() > 0) {
arr[pos++] = (int)bucket[j].pollFirst();
}
}
}
int cur = 0;
int h[];
int to[];
int ne[];
void add(int u, int v) {
to[cur] = v;
ne[cur] = h[u];
h[u] = cur++;
}
public boolean dfs(String cur, HashMap<String, Integer> vis, Map<String, List<String>> list, int cl) {
vis.put(cur, cl);
for (String hp : list.get(cur)) {
if (vis.containsKey(hp)) {
if (vis.get(hp) == cl) {
return false;
}
} else {
if (!dfs(hp, vis, list, 1 - cl)) {
return false;
}
}
}
return true;
}
public class MultiSet {
TreeMap<Integer, Integer> map;
int ct = 0;
MultiSet() {
map = new TreeMap<>();
}
public void remove(int key) {
if (map.containsKey(key)) {
int times = map.get(key);
if (times == 1) {
map.remove(key);
} else {
map.put(key, times - 1);
}
ct--;
}
}
public void add(int key) {
map.put(key, map.getOrDefault(key, 0) + 1);
ct++;
}
public int last() {
return map.lastKey();
}
public int first() {
return map.firstKey();
}
public int size() {
return ct;
}
}
BigInteger dp1[][];
int x[][];
BigInteger s(int l, int r, BigInteger a[]) {
if (l >= r)
return BigInteger.ZERO;
if (l + 1 == r) {
x[l][r] = l;
return (a[l].add(a[r])).multiply(a[l]);
}
if (!dp1[l][r].equals(BigInteger.valueOf(-1))) {
return dp1[l][r];
}
BigInteger ans = BigInteger.valueOf(Long.MIN_VALUE);
for (int j = l; j < r; ++j) {
BigInteger tp = (a[l].add(a[r])).multiply(a[j]).add(s(l, j, a)).add(s(j + 1, r, a));
if (tp.compareTo(ans) > 0) {
ans = tp;
x[l][r] = j;
}
}
return dp1[l][r] = ans;
}
TreeMap<Integer, ArrayList<Integer>> mp = new TreeMap<>();
void ss(int l, int r, int dep) {
if (l == r)
return;
int sp = x[l][r];
ArrayList<Integer> li = mp.getOrDefault(dep, new ArrayList<>());
li.add(sp + 1);
mp.put(dep, li);
ss(l, sp, dep + 1);
ss(sp + 1, r, dep + 1);
}
int color[], dfn[], low[], stack[];
int sccno[];
boolean iscut[];
int time = 0, top = 0;
int scc_cnt;
int dcc_cnt;
List<Integer> dcc[];
int root = 0;
// 无向图的强连通分量
void tarjanNonDirect(int u) {
low[u] = dfn[u] = ++time;
stack[top++] = u;
int child = 0;
for (int i = h[u]; i != -1; i = ne[i]) {
int v = to[i];
if (dfn[v] == 0) {
tarjanNonDirect(v);
low[u] = Math.min(low[u], low[v]);
if (low[v] >= dfn[u]) {
if (u != root || ++child > 1) { // 不是root，直接记为cut，是root，判断是否有两个儿子
iscut[u] = true;
}
++dcc_cnt;
// 一个割点可能会被多个点双共享
int z = -1;
do {
z = stack[--top];
//dcc[dcc_cnt].add(z);
} while (z != v);
//dcc[dcc_cnt].add(u);
}
} else {
low[u] = Math.min(low[u], dfn[v]);
// 没有特判是否直接指向父亲
// 回边，使用dfn【v】更新low【u】,因为可能是指向父亲，而父亲的low可能比较小
}
}
}
long dp11[][];
public long s(int l, int r, int a[]) {
if (l > r)
return 0;
if (dp11[l][r] != 0) {
return dp11[l][r];
}
if (l == r) {
return dp11[l][r] = a[l];
}
return dp11[l][r] = Math.max((long)a[l] - s(l + 1, r, a), (long)a[r] - s(l, r - 1, a));
}
long dp2[][];
public void dfs(int rt,int forb,boolean first){
dp2[rt][1] = 1;
vis[rt] = true;
int z = 0;
long add = -1000000000000000L;
for(int i=h[rt];i!=-1;i=ne[i]) {
int go = to[i];
if (go==forb) continue;
dfs(go, forb, false);
z++;
dp2[rt][1] += Math.max(dp2[go][0],dp2[go][1]);
add = Math.max(add , dp2[go][0] - Math.max(dp2[go][0],dp2[go][1]));
dp2[rt][0] += Math.max(dp2[go][0],dp2[go][1]);
}
if(first) {
if(z>0) {
dp2[rt][2] = dp2[rt][1];
dp2[rt][1] += add;
}else{
dp2[rt][1] = -1000000000000000L;
dp2[rt][2] = 1;
}
}else if(z>0) {
dp2[rt][1] += add;
}else{
dp2[rt][1] = -1000000000000000L;
}
}
int p[];
boolean vis[];
public int[] t(long a){
if(a==0){
return new int[2];
}
int f[] = new int[20];
int p = 1;
while(a>0){
int w = (int)(a%10);
f[p++] = w;
a/=10;
}
return Arrays.copyOf(f,p);
}
long mod = 1000000007;
public long s(int f[],long po[]){
long ans = 0;
outer:for(int sum=1;sum<=83;++sum) {
int prefix = 0;
long ps = 0;
for (int j = f.length - 1; j >= 1; --j) {
int c = f[j];
for(int q=0;q<c;++q){
int hou = sum - (q + prefix);
if(hou>=0) {
int qy = (int)(((q + ps*10L)*po[j]) % sum);
int hy = (sum - qy) % sum;
ans += ff[j - 1][sum][hy];
}
}
prefix += c;
ps = ps*10L+c;
ps %= sum;
if(prefix>sum){
continue outer;
}
}
if(sum==prefix && ps==0) {
ans ++;
}
}
return ans;
}
long dp3[][][][][];
long tot[];
long ff[][][];
int a[];
public void solve(int testNumber, InputReader in, PrintWriter out) {
int q[] = new int[100000];
int e = 0;
int st = 0;
int fk =1;
while(fk-->0){
int n = in.nextInt();
int a[] = in.nextArray(n);
int c[] = in.nextArray(n);
int mm = in.nextInt();
long dp[] = new long[mm+1];
Arrays.fill(dp,100000000);
dp[0] = 0;
for(int i=1;i<=n;++i){
int v = a[i-1];
int g = c[i-1];
long ndp[] = new long[mm+1];
for(int m=0;m<v;++m){
st = e = 0;
for(int j=0;j*v+m<=mm;j++){
while(st<e && q[st]<j-g) st++;
while(st<e && dp[v*q[e-1]+m] + (j-q[e-1])>= dp[v*j+m]) e--;
q[e++] = j;
ndp[j * v + m] = dp[v*q[st]+m] + (j-q[st]);
}
}
dp = ndp;
}
out.println(dp[mm]);
}
// long s= 0;
// for(int i=1;i<=97;++i){
// if(i%7==0||i%10==7||i/10==7||((i/10)+(i%10))%7==0) continue;
// s += i*i;
// }
// out.print(s);
// boolean f[] = new boolean[n+1];
//
// long r = 1;
// long mod = 1000000007;
// for(int j=2;j<=n;++j){
// if(!f[j]){
//
// for(int v=j*j;v<=n;v+=j){
// f[j] = true;
// }
// int nn = n;
// long s = 0;
// while(nn>0){
// s += nn/j;
// // s %= mod;
// nn /= j;
// }
// s *= 2;
// s++;
// s %= mod;
// r *= s;
// r %= mod;
// }
// }
// out.println(r);
// int t = 1;
//
//
// outer:for(int z=1;z<=t;++z) {
// int n = in.nextInt();
//
// h = new int[n+1000000];
// Arrays.fill(h,-1);
// to = new int[10*(n+1000000)];
// ne = new int[10*(n+1000000)];
//
//
//
// int a[] = in.nextArray(n);
//
//
// Arrays.sort(a);
// int x= 0;
// for(int i=0;i<n;++i){
// if(i==0||a[i]!=a[i-1]){
// a[x++] = a[i];
// }
// }
//
// int maxn = 10000000;
//
// int tot[] = new int[maxn+1];
//
// for(int u:a){
// tot[u]++;
// }
//
// int prime[] = new int[maxn + 1];
// int phi[] = new int[maxn+1];
// boolean visit[] = new boolean[maxn + 1];
// visit[1] = true;
// int minfactor[] = new int[maxn+1];
// minfactor[1] = 1;
// int mu[] = new int[maxn+1];
// mu[1]=1;
// int p = 0;
// for (int i = 2; i <= maxn; ++i) {
// if (!visit[i]) {
// prime[p++] = i;
// // prime
// phi[i] = i-1;
// minfactor[i] = i;
// mu[i] = -1;
// }
// for (int j = 0; j < p; ++j) {
// int check = i * prime[j];
// if( check > maxn){
// break;
// }
// visit[check] = true;
// minfactor[check] = prime[j];
// if (i % prime[j] == 0) {
// phi[ check ] = phi[i] * prime[j];
// mu[ check ] = 0;
// break;
// }
// mu[ check ] = -mu[i];
// phi[ check ] = phi[i] * (prime[j] - 1);
// }
// }
// int ct[] = new int[maxn+1];
// int id[] = new int[maxn+1];
// int from = 1;
//
// Map<Integer,Integer> old = new HashMap<>();
// for(int i=0;i<x;++i){
// ct[a[i]]++;
// id[a[i]] = from++;
// old.put(from-1,a[i]);
// }
//
// for(int i=0;i<p;++i){
// int v = prime[i];
// int cur = from++;
// for(int j=v;j<=maxn;j+=v){
// if(ct[j]>0){
// add(cur,id[j]);
// add(id[j],cur);
// }
// }
// }
// low =new int[from+1];
// dfn =new int[from+1];
// stack = new int[from+1];
// iscut = new boolean[from+1];
//
//
// for(int i=1;i<from;++i){
// tarjanNonDirect(i);
// }
// int r = 0;
// for(int i=1;i<from;++i){
// if(old.containsKey(i)&&iscut[i]&&tot[old.get(i)]==1){
// r++;
// }
// }
// out.println(r);
//
//
//
//
// }
// while(true) {
// int n = in.nextInt();
//
// int m =in.nextInt();
//
// fa = new int[n];
// dp = new int[n];
// for(int i=0;i<n;++i){
// fa[i] = i;
// }
// g = n;
// int c = 0;
// int as[] = new int[n];
// int bs[] = new int[n];
// char xs[] = new char[n];
//
// int at = -1;
// Set<Integer> st = new HashSet<>();
//
// for (int i = 0; i < n; ++i) {
// String line = in.next();
// int p = 0;
// int a = 0;
// while(Character.isDigit(line.charAt(p))){
// a = a*10 + (line.charAt(p)-'0'); p++;
// }
// char x = line.charAt(p++);
//
// int b = 0;
// while(p<line.length()){
// b = b*10 + (line.charAt(p)-'0'); p++;
// }
//
// as[i] = a;
// xs[i] = x;
// bs[i] = b;
//
// if(x=='='){
// int r1 = rt(a); int r2 = rt(b);
// if(r1==r2){
// if(dp[a]!=dp[b]){
// c++;
// at = i;
// }
// }else {
// combine(a, b, 0);
// }
// }else if(x=='<'){
// int r1 = rt(a); int r2 = rt(b);
// if(r1==r2){
// if(dp[a]>=dp[b]){
// c++;
// at = i;
// }
// }else {
// combine(a, b, -1);
// }
// }else{
// int r1 = rt(a); int r2 = rt(b);
// if(r1==r2){
// if(dp[a]<=dp[b]){
// c++;
// at = i;
// }
// }else {
// combine(a, b, 1);
// }
// }
//
//
// }
// if(g==1||c>=2){
// out.println("Impossible");
// continue;
// }
//
//
// for(int xuan: st){
//
//
//
//
// }
//
//
//
//
//
//
// }
}
static long mul(long a, long b, long p) {
long res = 0, base = a;
while (b > 0) {
if ((b & 1L) > 0)
res = (res + base) % p;
base = (base + base) % p;
b >>= 1;
}
return res;
}
static long mod_pow(long k, long n, long p) {
long res = 1L;
long temp = k % p;
while (n != 0L) {
if ((n & 1L) == 1L) {
res = mul(res, temp, p);
}
temp = mul(temp, temp, p);
n = n >> 1L;
}
return res % p;
}
public static double roundD(double result, int scale) {
BigDecimal bg = new BigDecimal(result).setScale(scale, RoundingMode.UP);
return bg.doubleValue();
}
}
private static void solve() {
InputStream inputStream = System.in;
// InputStream inputStream = null;
// try {
// inputStream = new FileInputStream(new File("D:\\chrome_download\\exp.out"));
// } catch (FileNotFoundException e) {
// e.printStackTrace();
// }
OutputStream outputStream = System.out;
// OutputStream outputStream = null;
// File f = new File("D:\\chrome_download\\");
// try {
// f.createNewFile();
// } catch (IOException e) {
// e.printStackTrace();
// }
// try {
// outputStream = new FileOutputStream(f);
// } catch (FileNotFoundException e) {
// e.printStackTrace();
// }
InputReader in = new InputReader(inputStream);
PrintWriter out = new PrintWriter(outputStream);
Task task = new Task();
task.solve(1, in, out);
out.close();
}
public static void main(String[] args) {
new Thread(null, () -> solve(), "1", (1 << 30)).start();
// solve();
}
static class InputReader {
public BufferedReader reader;
public StringTokenizer tokenizer;
public InputReader(InputStream stream) {
reader = new BufferedReader(new InputStreamReader(stream), 32768);
tokenizer = null;
}
public String nextLine() {
String line = null;
try {
line = reader.readLine();
} catch (IOException e) {
throw new RuntimeException(e);
}
return line;
}
public String next() {
while (tokenizer == null || !tokenizer.hasMoreTokens()) {
try {
tokenizer = new StringTokenizer(reader.readLine());
} catch (IOException e) {
throw new RuntimeException(e);
}
}
return tokenizer.nextToken();
}
public int nextInt() {
return Integer.parseInt(next());
}
public char nextChar() {
return next().charAt(0);
}
public int[] nextArray(int n) {
int res[] = new int[n];
for (int i = 0; i < n; ++i) {
res[i] = nextInt();
}
return res;
}
public long nextLong() {
return Long.parseLong(next());
}
public double nextDouble() {
return Double.parseDouble(next());
}
}
}
C++(g++ 7.5.0) 解法, 执行用时: 510ms, 内存消耗: 32512K, 提交时间: 2022-08-13 03:08:58
/*
*@author:bzdhxs
*@date:2022/08/13
*@URL:
*/
#include<bits/stdc++.h>
using namespace std;
template <typename T>
#define _orz ios::sync_with_stdio(false),cin.tie(0)
inline void read(T &s){s = 0;T w = 1, ch = getchar();while (!isdigit(ch)) { if (ch == '-') w = -1; ch = getchar(); }while (isdigit(ch)) { s = (s << 1) + (s << 3) + (ch ^48); ch = getchar();} s *= w;}
template <typename T>
inline void write(T s){if (s < 0) putchar('-'), s = -s;if (s > 9) write(s / 10);putchar(s % 10 + '0');}
#define int long long
#define endl "\n"
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int N = 1e6+10;
const int mod = 1e9+7;
int n,k;
int f[205][20005];
signed main()
{
cin >> n;
vector<int> b(n+1),c(n+1);
for(int i = 1;i <= n;i++) cin >> b[i];
for(int i = 1;i <= n;i++) cin >> c[i];
cin >> k;
memset(f,inf,sizeof(f));
f[0][0] = 0;
for(int i = 1;i <= n;i++)
for(int j = 0;j <= c[i];j++){
for(int o = b[i]*j;o <= k;o++){
f[i][o] = min(f[i][o],f[i-1][o-b[i]*j]+j);
}
}
cout << f[n][k] << endl;
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 39ms, 内存消耗: 1192K, 提交时间: 2020-01-08 22:44:08
#include<iostream>
#include<cstring>
#include<cstdio>
int n,m;
int dp[200005];
int v[2000005];
int c[2000005];
struct node{
int v;
int c;
}p[2000005];
using namespace std;
int main()
{
cin>>n;
int k;
for(int i=1;i<=n;i++){
cin>>c[i];
}
int cnt=0;
for(int i=1;i<=n;i++){
cin>>v[i];
for(int j=1;j<=v[i];j*=2){
p[++cnt].v=j;
p[cnt].c=j*c[i];
v[i]-=j;
}
p[++cnt].v=v[i];
p[cnt].c=v[i]*c[i];
}
cin>>k;
memset(dp,0x3f,sizeof(dp));
dp[0]=0;
for(int i=1;i<=cnt;i++){
for(int j=k;j>=p[i].c;j--){
dp[j]=min(dp[j],dp[j-p[i].c]+p[i].v);
}
}
cout<<dp[k]<<endl;
return 0;
}