目录
牛客.取金币
区间dp
找到重复子问题:找出整个数组能得到的最大积分，当拿走一个数字的时候，假如知道左边区域拿走金币的最大积分，右边区域拿走的最大积分，那么再加上中间这个数，拿走之后，不就是最大的积分
dp[i][j] :区间[i,j]的金币都拿走，能获得的最大积分是多少
最终结果
dp[0][n-1]
状态转移方程
此时会面对临界情况
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param coins int整型一维数组
* @return int整型
*/
public int getCoins (ArrayList<Integer> coins) {
int n=coins.size();
int[]a=new int[n+2];
for(int i=1;i<=n;i++){
a[i]=coins.get(i-1);
}
a[0]=1;
a[n+1]=1;
int[][]dp=new int[n+2][n+2];
for(int i=n;i>=1;i--){
for(int j=1;j<=n;j++){
for(int k=i;k<=j;k++){
dp[i][j]=Math.max(dp[i][k-1]+dp[k+1][j]+a[i-1]*a[k]*a[j+1],dp[i][j]);
}
}
}
return dp[1][n];
}
}力扣.四个选项
没怎么想明白，以为可以比如C3^12,C3^9,C3^6,然后就不咋不会写了,发现她这个是一个一个枚举，但是那我也没会写，没理解他的意思是啥，就写不出来
import java.util.*; public class Main{ static boolean[][]same=new boolean[13][13]; static int ret=0; //记录当前路径填哪些选项 static int[]path=new int[13]; static int []a=new int[5]; //cur是当前值 public static boolean isSame(int pos,int cur){ for(int i=0;i<pos;i++){ //假如和前面的不对，就是false if(same[i][pos]==true&&path[i]!=cur) return false; } return true; } public static void dfs(int pos){ if(pos>12) { ret++; return; } for(int i=1;i<=4;i++){ //看看有没有剩余次数 if(a[i]==0)continue; //假如当前位置应该喝某某位置一样，但是却不相同， if(!isSame(pos,i))continue; //这个位置不用回溯，因为会用其他的给覆盖住 path[pos]=i; a[i]--; dfs(pos+1); a[i]++; } } public static void main(String[]args){ Scanner in=new Scanner(System.in); for(int i=1;i<=4;i++){ a[i]=in.nextInt(); } int m=in.nextInt(); for(int i=0;i<m;i++){ int x=in.nextInt(); int y=in.nextInt(); same[x][y]=same[y][x]=true; } //从1位置开始计数 dfs(1); System.out.print(ret); } }
牛客.接雨水
思想，可以先求出，第一个柱子能存多少雨水，。。。只要我们能存每个柱子最多能存多少水
求出每一根柱子上能存多少雨水，把所有的柱子累加起来就可以
一根柱子上面最多存多少水？
和实际相结合，假如有这么多柱子，假如只往这一根柱子上下雨。
假如右边比你小，你下雨应该想给右边填满之后，然后在一起填
然后你假如更右边比你这个高之后，会到这个右边稍微高一点的停一下，直到把旁边那个也填满
换句话，她这个更偏向于，盛水左右的最大高度，，一个柱子能盛多少水，是看左右两边较高的给他挡着，不然就会溢出出，受左右两边较高的柱子里面，较低的那个柱子影响
lmax[i],rmax[i]左右两个高的柱子，然后最小值
把从0到最后，每一根柱子里面
min(left[i],right[i])-height[i]
预处理两个数组，left[i]和right[i]，从0到i 和从i到n-1柱子 （细节就是我们要考虑当前这根柱子，因为有可能我们当前柱子就是最大值，此时左侧和右侧最大会出现负数，所以包含自己，那么减去就是0） 里面的最大值
这个解法，纯纯五星，就是非常好理解
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * max water * @param arr int整型一维数组 the array * @return long长整型 */ public long maxWater (int[] arr) { int n=arr.length; int[]left=new int[n]; int[]right=new int[n]; left[0]=arr[0]; for(int i=1;i<n;i++){ left[i]=Math.max(left[i-1],arr[i]); } right[n-1]=arr[n-1]; for(int i=n-2;i>=0;i--){ right[i]=Math.max(right[i+1],arr[i]); } long sum=0; for(int i=1;i<n-1;i++){ sum+=Math.min(left[i],right[i])-arr[i]; } return sum; } }
牛客.加减
贪心，尽量选择一些比较挨的近的数，让他们变成相同
排序:枚举所有的区间，找出区间内所有数变成相同的数的最小代价，cost<=k
区间长度
此时你进行找的时候，会超时的，所以，枚举区间内最小代价，
如何求，一个区间的最小代价cost, （数学问题，数轴上有一些点，选取一个位置，使所有点到到他的位置最小
结论:选择最中间的点，花费的代价最小（点，不是数）
cost: a3-a3. ,a3-a2 a3-a1 a4-a3 a5-a3
假如是a3 右边的点 偏移量为x
a3-a3+变化量x
a3+变化量x-a2
a3+变化量x-a1
a4-变化量x-a3
a5-a3-变化量x 其中 第二个和第三个都是+变化量 ，第4和5都是-变化量
上面那个图，变化量x就是a3到x的距离。
假如偶数的点，那么你左右都可以。
优化一：前缀和求最小代价cost
cost=a3-a2 +a3-a1 + a4-a3+ a5-a3+ a6-a3
= 2*a3 - (a1+a2)+ (a4+a5+a6) - 3*a3 (求一段区间内，快速求，使用前缀和)
第二个优化:
滑动窗口来优化，
1 ， 3， 6 ，8 ，20
left
right
import java.util.*; public class Main{ static int n; static long []sum; static long[]a; public static long cal(int l,int r){ int mid=(l+r)/2; return (mid-l)*a[mid]-(sum[mid-1]-sum[l-1])+ (sum[r]-sum[mid])-(r-mid)*a[mid]; } public static void main(String[]args){ Scanner in=new Scanner(System.in); n=in.nextInt(); long k=in.nextLong(); sum=new long[n+1]; a=new long[n+1]; for(int i=1;i<=n;i++){ a[i]=in.nextLong(); } Arrays.sort(a); //前缀和 for(int i=1;i<=n;i++){ sum[i]=sum[i-1]+a[i]; } int l=1; int r=1; long ret=1; while(r<=n){ long cost=cal(l,r); while(cost>k){ l++; cost=cal(l,r); } ret=Math.max(r-l+1,ret); r++; } System.out.print(ret); } }
