题目链接：
题意：
给定n q 表示有n个石头 q个询问
下面n个数字给出每个石头的价值
下面n个数字给出每个石头的颜色（用1-n表示）
选出一个子序列使得序列的权值和最大（序列权值计算方式：当这个点的颜色和前面那个点颜色相同时 贡献 value * a, otherwise 贡献 value * b）
下面q行，每行给出 a 和 b的值。
思路：
首先求dp方程 dp[i]表示颜色为i时的最大值 那么 this_point_value = max(dp[j] + b*v[i]) (i!=j) this_point_value = max(dp[i] + a*v[i]) dp[color[i]] =this_point_value;
就是这样。
import java.io.BufferedReader;import java.io.InputStreamReader;import java.io.PrintWriter;import java.math.BigInteger;import java.text.DecimalFormat;import java.util.ArrayDeque;import java.util.ArrayList;import java.util.Arrays;import java.util.Collection;import java.util.Collections;import java.util.Comparator;import java.util.Deque;import java.util.HashMap;import java.util.Iterator;import java.util.LinkedList;import java.util.Map;import java.util.PriorityQueue;import java.util.Scanner;import java.util.Stack;import java.util.StringTokenizer;import java.util.TreeMap;import java.util.TreeSet;import java.util.Queue;import java.io.File;import java.io.FileInputStream;import java.io.FileNotFoundException;import java.io.FileOutputStream;public class Main {int n, q, a, b;int[] v = new int[N], c = new int[N];long[] dp = new long[N];int[] pre = new int[N];long max1, max2;int col1, col2;void up(long val, int col){if(val>=max1){if(val>max1){if(col == col1){max1 = val;}else {max2 = max1; col2 = col1;max1 = val; col1 = col;}}else if(col!=col1){max2 = val; col2 = col;}}else if(val >= max2){if(col == col1)return;max2 = val; col2 = col;}}void work() throws Exception{n = Int(); q = Int();for(int i = 1; i <= n; i++)v[i] = Int();for(int i = 1; i <= n; i++)c[i] = Int();while(q–>0){a = Int(); b = Int();long ans = 0;max1 = -inf64; max2 = -inf64;col1 = 0; col2 = 0;for(int i = 1; i <= n; i++)pre[i] = -1;for(int i = 1; i <= n; i++){long now = (long)v[i]*b;if(pre[c[i]]!=-1){now = max(now, dp[c[i]] + (long)a*v[i]);//out.print("now1:"+now);}if(col1!=c[i] && col1!=0)now = max(now, max1 + (long)b*v[i]);else if(col2!=c[i] && col2!=0)now = max(now, max2 + (long)b*v[i]);//out.println(" now2:"+now);up(now, c[i]);if(pre[c[i]] == -1)dp[c[i]] = now;elsedp[c[i]] = max(dp[c[i]], now);pre[c[i]] = i;ans = max(ans, now);//out.println(max1+" "+col1);out.println(max2+" "+col2);out.println(now+" "+ans+" ***");}out.println(ans);}}public static void main(String[] args) throws Exception{Main wo = new Main();in = new BufferedReader(new InputStreamReader(System.in));out = new PrintWriter(System.out); // in = new BufferedReader(new InputStreamReader(new FileInputStream(new File("input.txt")))); // out = new PrintWriter(new File("output.txt"));wo.work();out.close();}static int N = 100000+5;static int M = 101;DecimalFormat df=new DecimalFormat("0.0000");static int inf = (int)1e9;static long inf64 = (long) 1e18;static double eps = 1e-8;static double Pi = Math.PI;static int mod = (int)1e9 + 7 ;private String Next() throws Exception{while (str == null || !str.hasMoreElements())str = new StringTokenizer(in.readLine());return str.nextToken();}private int Int() throws Exception{return Integer.parseInt(Next());}private long Long() throws Exception{return Long.parseLong(Next());}private double Double() throws Exception{return Double.parseDouble(Next());}StringTokenizer str;static Scanner cin = new Scanner(System.in);static BufferedReader in;static PrintWriter out; /* class Edge{int from, to, dis, nex;Edge(){}Edge(int from, int to, int dis, int nex){this.from = from;this.to = to;this.dis = dis;this.nex = nex;}}Edge[] edge = new Edge[M<<1];int[] head = new int[N];int edgenum;void init_edge(){for(int i = 0; i < N; i++)head[i] = -1; edgenum = 0;}void add(int u, int v, int dis){edge[edgenum] = new Edge(u, v, dis, head[u]);head[u] = edgenum++;}/**/int upper_bound(int[] A, int l, int r, int val) {// upper_bound(A+l,A+r,val)-A;int pos = r;r–;while (l <= r) {int mid = (l + r) >> 1;if (A[mid] <= val) {l = mid + 1;} else {pos = mid;r = mid – 1;}}return pos;}int Pow(int x, int y) {int ans = 1;while (y > 0) {if ((y & 1) > 0)ans *= x;y >>= 1;x = x * x;}return ans;}double Pow(double x, int y) {double ans = 1;while (y > 0) {if ((y & 1) > 0)ans *= x;y >>= 1;x = x * x;}return ans;}int Pow_Mod(int x, int y, int mod) {int ans = 1;while (y > 0) {if ((y & 1) > 0)ans *= x;ans %= mod;y >>= 1;x = x * x;x %= mod;}return ans;}long Pow(long x, long y) {long ans = 1;while (y > 0) {if ((y & 1) > 0)ans *= x;y >>= 1;x = x * x;}return ans;}long Pow_Mod(long x, long y, long mod) {long ans = 1;while (y > 0) {if ((y & 1) > 0)ans *= x;ans %= mod;y >>= 1;x = x * x;x %= mod;}return ans;}int gcd(int x, int y){if(x>y){int tmp = x; x = y; y = tmp;}while(x>0){y %= x;int tmp = x; x = y; y = tmp;}return y;}int max(int x, int y) {return x > y ? x : y;}int min(int x, int y) {return x < y ? x : y;}double max(double x, double y) {return x > y ? x : y;}double min(double x, double y) {return x < y ? x : y;}long max(long x, long y) {return x > y ? x : y;}long min(long x, long y) {return x < y ? x : y;}int abs(int x) {return x > 0 ? x : -x;}double abs(double x) {return x > 0 ? x : -x;}long abs(long x) {return x > 0 ? x : -x;}boolean zero(double x) {return abs(x) < eps;}double sin(double x){return Math.sin(x);}double cos(double x){return Math.cos(x);}double tan(double x){return Math.tan(x);}double sqrt(double x){return Math.sqrt(x);}}
，才能做到人在旅途，感悟人生，享受人生。
