三道编程
第一题 （AC）
类似于linux系统下，文件路径的前进和后退以及输出当前路径的指令。
思路：直接模拟就可以，不过每一行用的nextInt()和next()接收数据的时候需要注意用nextLine()把回车吃掉。
输入：
7
cd a
cd b
pwd
cd ..
pwd
cd ..
pwd
输出：
/a/b
/a
/
第二题 （18%）
给定n，k，然后给n个数。划分数组，最多为k个分段，每个分段内部的val表示为max-min。输出：任意划分，使得val最小。
思路：读完数据，输出“2”，偷了18%；输出“4”，9%；如果没有k的限制，默认会有n个分段，题目还规定，分段中一个数的时候，val = 0。所以大概要找一种方法，就是在n-1个间隙内进行两两合并，还要保证val最小。
第三题 （AC）
给定n，m。然后给一个长度为n的由1和0组成的字符串，再给m组数据（c，v），每组数据表示连续的c个1消除之后，可以获取v。输出整个字符串的1全部消除之后的最大价值；
n:[1,100000], m:[1,100]
思路：字符串中的0是没有作用的，所以先使用 split 函数根据 “0” 将字符串切分为连续1组成的字符串数组，然后转变为字符串长度的数组，即 int[] num。开始想的是将m个切分条件放入结构体按照v/c排序，直接对字符串长度取模求结果，但是这样比较的是单个1的价值，没有考虑连续1消除的条件，只能看运气拿分。
写道num数组这里，突然想起来完全背包，然后看了下n和m的取值区间，max(n*m) <= 1e7 < 1e8.最坏的情况，字符串中全部为1，时间复杂度为o(nm)，所以不会超时。这里完全背包使用了一维滚动数组，所以m从前向后遍历，复用上次遍历的结果。
输入：
11 2
11111101111
3 10
4 15
输出：
35
import java.util.* ;
public class Main{
public static void main(String[] args) {
Scanner in = new Scanner(System.in) ;
int n = in.nextInt() ;
int m = in.nextInt() ;
in.nextLine() ;
String s = in.nextLine() ;
int[] v = new int[m] ;
int[] c = new int[m] ;
for(int i = 0; i<m; ++i) {
c[i] = in.nextInt() ;
v[i] = in.nextInt() ;
}
String[] t = s.split("0") ;
int len = t.length ;
int[] num = new int[len] ;
int maxx = -1 ;
int ans = 0 ;
for(int i = 0; i<len; ++i) {
num[i] = t[i].length();
maxx = num[i];
int[] dp = new int[maxx + 1];
dp[0] = 0 ;
for (int j = 1; j <= maxx; ++j) {
for (int k = 0; k < m; ++k) {
if (c[k] <= j) {
dp[j] = Math.max(dp[j - c[k]] + v[k], dp[j]);
}
}
}
ans += dp[maxx] ;
}
System.out.println(ans) ;
}
}