publicclassLongestIncreasingSubsequence{ publicstaticvoidmain(String[] args){ Scanner sc = new Scanner(System.in); while (sc.hasNext()) { int n = sc.nextInt(); int[] a = newint[n]; for (int i = 0; i < n; i++) { a[i] = sc.nextInt(); } System.out.println(lis_NN(a)); } } publicstaticintlis_NN(int[] a){// 时间复杂度为O(n*n) int n = a.length; int[] dp = newint[n]; int[] pi = newint[n]; int i, j, p = 0; for (i = 0; i < n; i++) { dp[i] = 1;// 初值置为1，代表长度至少为1// 初始化为1，长度最短为自身 pi[i] = -1; } int max = 1;// 最大长度 for (i = 1; i < n; i++) { for (j = 0; j < i; j++) {// 对i前每一个数字进行判断 if (a[j] < a[i]) {// 若该i值 dp[i] = Math.max(dp[j] + 1, dp[i]);// ！！！ if (dp[j] + 1 == dp[i]) { pi[i] = j;// 记录选择 } } } max = Math.max(dp[i], max);// 进行比较 if (dp[i] == max) {// 这个判断是为了记录选择 p = i; } } int[] seq = newint[max]; for (i = max - 1; i >= 0; i--) { seq[i] = a[p]; p = pi[p]; } for (i = 0; i < max; i++) { System.out.print(seq[i]); }
return max; } publicstaticintlis_NlogN(int[] a){//时间复杂度为O(n*logN) int n = a.length; int[] dp = newint[n + 1];//因为dp下标从1开始，故为长度n+1 dp[1] = a[0];//默认至少有一个数字 int index = 1;//dp的下标 for (int i = 1; i < n; i++) { if (a[i] > dp[index]) {//若a[i]大于dp数组最大值，则直接添加 dp[++index] = a[i]; } else {//否则找到dp中第一个大于等于a[i]的位置，用a[i]替换之。 int tempIndex = BinarySearch(dp, index, a[i]);//需自定义二分查找，否则找不到时会出现-1，数组越界 dp[tempIndex] = a[i]; } } return index; } // 二分查找变体 找到第一个大于n的位置index privatestaticintBinarySearch(int[] dp, int len, int n){ int left = 1; int right = len; while (right > left) { int mid = (left + right) / 2; if (dp[mid] == n) { return mid; } elseif (dp[mid] < n) { left = mid + 1; } else { right = mid;//注意这里不能为right = mid -1; } } return right; } }
Given a 2D grid, each cell is either a wall 'W', an enemy 'E' or empty '0' (the number zero), return the maximum enemies you can kill using one bomb. The bomb kills all the enemies in the same row and column from the planted point until it hits the wall since the wall is too strong to be destroyed. Note that you can only put the bomb at an empty cell.
Example:
1 2 3 4 5 6 7
For the given grid
0 E 0 0 E 0 W E 0 E 0 0
return 3.
思路：
分上下左右四个方向，定义四个数组
向上能炸死多少敌人：之前上面炸死的人，加上本格炸死的人
如果想打印每次决策的路径，则需要记录下每一次选择
1 2
传纸条
Problem
从左上传到右下，和从右下传到左上，同一个格子不能重复使用，求途径格子和最大值
可以看做两个左上传递到右下，枚举两个格子进行dp，还有个特性，就是两个格子的横轴坐标和相等
1 2 3 4 5 6 7
双线程DP（四维DP) //双线程dp.....f[x1][y1][x2][y2]是当一次传纸条在(x1,y1)第二次在(x2,y2)时的最大值 int a1=max(dp[i-1][j][k-1][l],dp[i-1][j][k][l-1]); int a2=max(dp[i][j-1][k-1][l],dp[i][j-1][k][l-1]); dp[i][j][k][l]=max(a1,a2)+a[i][j]+a[k][l]; if(i==k && j==l) {dp[i][j][k][l]-=a[i][j];} 每次选择最大值，两个DP同时进行，如果有冲突的话，一个暂停一步（减去a[i] [j]或者是a[k] [l]），这样就错开了