多重部分和问题
package Test.ACM;
import java.io.*;
import java.util.*;
import java.math.*;
/*
定义：dp[i][j] 为前i种硬币组成面值为j时第i种币值剩下的个数，-1表示不能组成
这样定义一般要这样规范：i最好为1~n
初始化：dp[i][0] = cnt[i]
dp[0][j] = -1，表示前0种币值无论如何都不能组成面值为j
关键点：dp[0][0] = 0
最后就是处理边界情况
3 10
1 2 4 2 1 1
2 5
1 4 2 1
0 0
*/
public class Main {
public static void main(String[] args) {
InputReader in = new InputReader();
PrintWriter out = new PrintWriter(System.out);
while(in.hasNext()) {
int n = in.nextInt();
int m = in.nextInt();
if(n == 0 && m == 0) break;
int[] val = new int[n + 1];
int[] cnt = new int[n + 1];
int[][] dp = new int[n + 1][m + 1];
for(int i = 1; i <= n; ++i) {
val[i] = in.nextInt();
}
for(int i = 1; i <= n; ++i) {
cnt[i] = in.nextInt();
}
for(int i = 0; i <= n; ++i) {
for(int j = 0; j <= m; ++j) {
dp[i][j] = -1;
}
}
for(int i = 1; i <= n; ++i) { // 注意初始化
dp[i][0] = cnt[i];
}
dp[0][0] = 0; // 关键点
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= m; ++j) { // 遍历所有面值
if(dp[i - 1][j] >= 0) { // 如果前i种硬币已能够凑成j，那么不必花费第i种硬币
dp[i][j] = cnt[i];
// 不满足即 dp[i - 1][j] < 0
}else if(j < val[i]) { // 如果当前第i种币值大于j，显然当前第i种币值也不能组成面值为j，赋值为-1
dp[i][j] = -1;
}else if(dp[i][j - val[i]] <= 0) {
// j >= val[i]，若花费a个val[i]能组成j，那么花费a-1个val[i]也能组成j-val[i]
// 当前j剩余的个数不大于0时，赋值为-1
dp[i][j] = -1;
}else { // 否则为上一个状态dp[i][j- val[i]] - 1
dp[i][j] = dp[i][j - val[i]] - 1;
}
}
}
int ans = 0;
for(int j = 1; j <= m; ++j) {
if(dp[n][j] >= 0) ++ans; // 统计前n种硬币能组成1~m的个数
}
out.println(ans);
out.flush();
}
out.close();
}
}
class InputReader {
BufferedReader buf;
StringTokenizer tok;
InputReader() {
buf = new BufferedReader(new InputStreamReader(System.in));
}
boolean hasNext() {
while(tok == null || !tok.hasMoreElements()) {
try {
tok = new StringTokenizer(buf.readLine());
}
catch(Exception e) {
return false;
}
}
return true;
}
String next() {
if(hasNext()) return tok.nextToken();
return null;
}
int nextInt() {
return Integer.parseInt(next());
}
long nextLong() {
return Long.parseLong(next());
}
double nextDouble() {
return Double.parseDouble(next());
}
BigInteger nextBigInteger() {
return new BigInteger(next());
}
BigDecimal nextBigDecimal() {
return new BigDecimal(next());
}
}
package Test.ACM;
import java.io.*;
import java.util.*;
import java.math.*;
/*
定义：dp[i][j] 为前i种硬币组成面值为j时第i种币值剩下的个数，-1表示不能组成
这样定义一般要这样规范：i最好为1~n
初始化：dp[i][0] = cnt[i]
dp[0][j] = -1，表示前0种币值无论如何都不能组成面值为j
关键点：dp[0][0] = 0
最后就是处理边界情况
因为每个状态至于上一个状态有关，故可以压缩为一维数组实现
3 10
1 2 4 2 1 1
2 5
1 4 2 1
0 0
*/
public class Main {
public static void main(String[] args) {
InputReader in = new InputReader();
PrintWriter out = new PrintWriter(System.out);
while(in.hasNext()) {
int n = in.nextInt();
int m = in.nextInt();
if(n == 0 && m == 0) break;
int[] val = new int[n + 1];
int[] cnt = new int[n + 1];
int[] dp = new int[m + 1];
for(int i = 1; i <= n; ++i) {
val[i] = in.nextInt();
}
for(int i = 1; i <= n; ++i) {
cnt[i] = in.nextInt();
}
for(int j = 0; j <= m; ++j) {
dp[j] = -1;
}
dp[0] = 0;
for(int i = 1; i <= n; ++i) {
for(int j = 0; j <= m; ++j) { // 没有初始化真实值，j要从0开始
if(dp[j] >= 0) dp[j] = cnt[i]; // 逐渐从上一个状态转移过来
else if(j < val[i] || dp[j - val[i]] <= 0) {
dp[j] = -1;
}else {
dp[j] = dp[j - val[i]] - 1;
}
}
}
int ans = 0;
for(int j = 1; j <= m; ++j) {
if(dp[j] >= 0) ++ans;
}
out.println(ans);
out.flush();
}
out.close();
}
}
class InputReader {
BufferedReader buf;
StringTokenizer tok;
InputReader() {
buf = new BufferedReader(new InputStreamReader(System.in));
}
boolean hasNext() {
while(tok == null || !tok.hasMoreElements()) {
try {
tok = new StringTokenizer(buf.readLine());
}
catch(Exception e) {
return false;
}
}
return true;
}
String next() {
if(hasNext()) return tok.nextToken();
return null;
}
int nextInt() {
return Integer.parseInt(next());
}
long nextLong() {
return Long.parseLong(next());
}
double nextDouble() {
return Double.parseDouble(next());
}
BigInteger nextBigInteger() {
return new BigInteger(next());
}
BigDecimal nextBigDecimal() {
return new BigDecimal(next());
}
}
- poj 3280 Cheapest Palindrome （区间DP）
- 记忆化搜索
package Test.ACM;
import java.io.*;
import java.util.*;
import java.math.*;
/*
定义：dp[i][j]为区间[i,j]删去某些字符后得到的最小代价
3 4
abcb
a 1000 1100
b 350 700
c 200 800
*/
public class Main {
static char[] chars = new char[2005];
static int[][] dp = new int[2005][2005];
static int[] cost = new int[26];
public static void main(String[] args) {
InputReader in = new InputReader();
PrintWriter out = new PrintWriter(System.out);
while(in.hasNext()) {
int n = in.nextInt();
int m = in.nextInt();
String str = in.next();
chars = str.toCharArray();
for(int i = 0; i <= m; ++i) {
for(int j = 0; j <= m; ++j) {
dp[i][j] = -1;
}
}
for(int i = 1; i <= n; ++i) {
str = in.next();
int x = in.nextInt();
int y = in.nextInt();
cost[str.charAt(0) - 'a'] = Math.min(x, y);
}
out.println(dfs(0, m - 1));
out.flush();
}
out.close();
}
public static int dfs(int lt, int rt) {
if(lt >= rt) return dp[lt][rt] = 0;
else if(dp[lt][rt] != -1) return dp[lt][rt];
else if(chars[lt] == chars[rt]) return dp[lt][rt] = dfs(lt + 1, rt - 1);
else return dp[lt][rt] = Math.min(dfs(lt + 1, rt) + cost[chars[lt] - 'a'], dfs(lt , rt - 1) + cost[chars[rt] - 'a']);
}
}
class InputReader {
BufferedReader buf;
StringTokenizer tok;
InputReader() {
buf = new BufferedReader(new InputStreamReader(System.in));
}
boolean hasNext() {
while(tok == null || !tok.hasMoreElements()) {
try {
tok = new StringTokenizer(buf.readLine());
}
catch(Exception e) {
return false;
}
}
return true;
}
String next() {
if(hasNext()) return tok.nextToken();
return null;
}
int nextInt() {
return Integer.parseInt(next());
}
long nextLong() {
return Long.parseLong(next());
}
double nextDouble() {
return Double.parseDouble(next());
}
BigInteger nextBigInteger() {
return new BigInteger(next());
}
BigDecimal nextBigDecimal() {
return new BigDecimal(next());
}
}
网友评论