题目链接

Dollar Dayz POJ - 3181

思路

$$ \begin{aligned}挑战程序设计上写的没太懂，再看看\\\\这就是个完全背包。。。\\\\取模多好，非得弄成大数题。。。\end{aligned} $$

时间复杂度

$$ O(NK) $$

代码

import java.io.*;
import java.math.*;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args){
        InputStream inputStream = System.in;//new FileInputStream("C:\\Users\\wavator\\Downloads\\test.in");
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        Task solver = new Task();
        solver.solve(in, out);
        out.close();
    }

    static class Task {


        BigInteger dp[][] = new BigInteger[105][1005];

        public void solve(InputReader in, PrintWriter out) {
            while (in.hasNext()) {
                // do sth

                int n = in.nextInt();
                int k = in.nextInt();

                dp[0][0] = BigInteger.ONE;
                for (int i = 1; i <= n; i++) {
                    dp[0][i] = BigInteger.ZERO;
                }

                for (int i = 1; i <= k; i++) {
                    for (int j = 0; j <= n; j++) {
                        if (j - i >= 0) {
                            dp[i][j] = dp[i - 1][j].add(dp[i][j - i]);
                        } else {
                            dp[i][j] = dp[i - 1][j];
                        }
                    }
                }

                out.println(dp[k][n]);

                out.flush();
            }
        }

    }

    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        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 long nextLong() {
            return Long.parseLong(next());
        }

        public double nextDouble() {
            return Double.parseDouble(next());
        }

        public char[] nextCharArray() {
            return next().toCharArray();
        }

        //         public boolean hasNext() {
//             try {
//                 return reader.ready();
//             } catch(IOException e) {
//                 throw new RuntimeException(e);
//             }
//         }
        public boolean hasNext() {
            try {
                String string = reader.readLine();
                if (string == null) {
                    return false;
                }
                tokenizer = new StringTokenizer(string);
                return tokenizer.hasMoreTokens();
            } catch(IOException e) {
                return false;
            }
        }
        public BigInteger nextBigInteger() {
            return new BigInteger(next());
        }

        public BigDecimal nextBigDecinal() {
            return new BigDecimal(next());
        }
    }
}

完全背包

import java.io.*;
import java.math.*;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args){
        InputStream inputStream = System.in;//new FileInputStream("C:\\Users\\wavator\\Downloads\\test.in");
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        Task solver = new Task();
        solver.solve(in, out);
        out.close();
    }

    static class Task {


        BigInteger dp[][] = new BigInteger[105][1005];

        public void solve(InputReader in, PrintWriter out) {
            while (in.hasNext()) {
                // do sth

                int n = in.nextInt();
                int k = in.nextInt();

                BigInteger dp[] = new BigInteger[1005];
                dp[0] = BigInteger.ONE;
                for (int i = 1; i <= n; i++) {
                    dp[i] = BigInteger.ZERO;
                }
                for (int i = 1; i <= k; i++) {
                    for (int j = 1; j <= n; j++) {
                        if (j - i >= 0) {
                            dp[j] = dp[j].add(dp[j - i]);
                        }
                    }
                }
                out.println(dp[n]);
                out.flush();
            }
        }

    }

    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        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 long nextLong() {
            return Long.parseLong(next());
        }

        public double nextDouble() {
            return Double.parseDouble(next());
        }

        public char[] nextCharArray() {
            return next().toCharArray();
        }

        //         public boolean hasNext() {
//             try {
//                 return reader.ready();
//             } catch(IOException e) {
//                 throw new RuntimeException(e);
//             }
//         }
        public boolean hasNext() {
            try {
                String string = reader.readLine();
                if (string == null) {
                    return false;
                }
                tokenizer = new StringTokenizer(string);
                return tokenizer.hasMoreTokens();
            } catch(IOException e) {
                return false;
            }
        }
        public BigInteger nextBigInteger() {
            return new BigInteger(next());
        }

        public BigDecimal nextBigDecinal() {
            return new BigDecimal(next());
        }
    }
}