1464277362
问题描述
小明正在玩一个“翻硬币”的游戏。
桌上放着排成一排的若干硬币。我们用 * 表示正面，用 o 表示反面（是小写字母，不是零）。
比如，可能情形是：oo*oooo
如果同时翻转左边的两个硬币，则变为：oooo***oooo
现在小明的问题是：如果已知了初始状态和要达到的目标状态，每次只能同时翻转相邻的两个硬币,那么对特定的局面，最少要翻动多少次呢？
我们约定：把翻动相邻的两个硬币叫做一步操作，那么要求：
输入格式
两行等长的字符串，分别表示初始状态和要达到的目标状态。每行的长度<1000
输出格式
一个整数，表示最小操作步数。
样例输入1
oo
样例输出1
5
样例输入2
o*oo
o**oo*
样例输出2
1
代码实现
import java.util.Scanner;
/**
翻硬币
@author Ape
/
public class Fanyb {static int[] hash = new int[1001];
static String s1, s2;
static int vis = -1, ans = 0;public static void main(String[] args) {
Scanner scanner = new Scanner(System.in); s1 = scanner.nextLine(); s2 = scanner.nextLine(); for (int i = 0; i < s1.length(); i++) if (s1.charAt(i) == s2.charAt(i)) hash[i] = 0; else hash[i] = 1; for (int i = 0; i < s1.length(); i++) if (hash[i] == 1) { // 检测到不相同 if (vis == -1) // 如果前面没有记录的1的下标，记录当前1的下标 vis = i; else { ans += i - vis; vis = -1; } } System.out.println(ans); scanner.close();}
}
问题描述
给定N个物品,每个物品有一个重量W和一个价值V.你有一个能装M重量的背包.问怎么装使得所装价值最大.每个物品只有一个.
输入格式
输入的第一行包含两个整数n, m，分别表示物品的个数和背包能装重量。
以后N行每行两个数Wi和Vi,表示物品的重量和价值
输出格式
输出1行，包含一个整数，表示最大价值。
样例输入
3 5
2 3
3 5
4 7
样例输出
8
数据规模和约定
1<=N<=200,M<=5000.
代码实现
import java.util.Scanner;
/**
@author Ape
/
public class DpBeiBao {static int[] w = new int[201]; // 物品重量
static int[] p = new int[201]; // 物品价值
static int n, W; // W背包重量public static void main(String[] args) {
Scanner scanner = new Scanner(System.in); n = scanner.nextInt(); W = scanner.nextInt(); for (int i = 0; i < n; i++) { w[i] = scanner.nextInt(); p[i] = scanner.nextInt(); } int[] b = new int[W + 1]; // 数组下标为背包的重量,值为当前重量的价值 for (int i = 0; i < w.length; i++) for (int j = W; j >= w[i]; j--) // 以不超过背包最大重量前提计算物品最大值 if (b[j - w[i]] + p[i] > b[j]) b[j] = b[j - w[i]] + p[i]; System.out.println(b[W]); scanner.close();}
}
ps:距离比赛还有一天，哈哈，北京我来了