1464303700
昨晚1点半才睡，为的是这两题，今早6点起来现在已经整顿好淡定的发博客
一题是省赛压轴题，为何我一看代码思路全明了捏，当时想死都想不出
题目描述
密码脱落
X星球的考古学家发现了一批古代留下来的密码。
这些密码是由A、B、C、D 四种植物的种子串成的序列。
仔细分析发现，这些密码串当初应该是前后对称的（也就是我们说的镜像串）。
由于年代久远，其中许多种子脱落了，因而可能会失去镜像的特征。
你的任务是：
给定一个现在看到的密码串，计算一下从当初的状态，它要至少脱落多少个种子，才可能会变成现在的样子。
输入一行，表示现在看到的密码串（长度不大于1000）
要求输出一个正整数，表示至少脱落了多少个种子。
例如，输入：
ABCBA
则程序应该输出：
0
再例如，输入：
ABECDCBABC
则程序应该输出：
3
资源约定：
峰值内存消耗（含虚拟机） < 256M
CPU消耗 < 3000ms
代码实现
import java.util.Scanner;
/**
@author Ape
/
public class A10 {static char[] s = new char[1000];
static int min = 0, num = 0;static void fcode(int left, int right, int num) {
if (left >= right) { min = min < num ? min : num; } else { if (s[left] == s[right]) { fcode(left + 1, right - 1, num); } else { fcode(left + 1, right, num + 1); fcode(left, right - 1, num + 1); } } return;}
public static void main(String[] args) {
// TODO Auto-generated method stub Scanner scanner = new Scanner(System.in); String str = scanner.nextLine(); s = str.toCharArray(); min = s.length; fcode(0, min - 1, 0); System.out.println(min); scanner.close();}
}
题目占时找不到了，看代码可以找到什么意思，准备出发
import java.util.Scanner;
public class DpShop {
static final int MAX = 10001;
static int[] p = new int[MAX];
static int[] w = new int[MAX];
static int W, n, ans = 0;
static void dfs(int value, int vn) {
if (n == vn)
return;
if (value > 1000)
return;
if (value == 1000) {
ans++;
for (int i = 0; i < n; i++)
System.out.print(w[i] + " ");
System.out.println();
} else {
dfs(value, vn + 1);
if (value + p[vn] <= 1000) {
w[vn]++;
dfs(value + p[vn], vn);
w[vn]--;
}
}
}
static void f(int total, int size) {
if (size != n) {
if (total == 0)// 判断背包是否正装满
{
ans++;// 存放可行方案的个数
for (int i = 0; i < n; i++)
System.out.print(w[i] + " ");
System.out.println();
} else {
f(total, size + 1);// 未放入物品a【size】的情况
if (total - p[size] >= 0)// 判断放入a【size】后，是否会超出背包的承载
{
w[size]++;// 使得a【size】对应物品的数量加1
f(total - p[size], size);// 放入物品a[size]的情况
w[size]--;// 使得相应的物品数量减1
}
}
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
n = scanner.nextInt();
for (int i = 0; i < n; i++)
p[i] = scanner.nextInt();
// f(1000, 0);
dfs(0, 0);
scanner.close();
}}