//dp[i] 表示以颜色为i结尾的最大值
//dp[i] = max(dp[i] , dp[i] + a*v[i] ,other_max + b*v[i]) ;
//为除颜色i以外的其它颜色的最大值
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std ;
const int maxn = 100010 ;
const __int64 inf = 0x7fffffffffffffff;
__int64 dp[maxn] ;
__int64 c[maxn] ;
__int64 v[maxn] ;
int main()
{
// freopen("input.txt","r" ,stdin) ;
int n , q;
while(~scanf("%d%d" ,&n ,&q))
{
for(int i = 1;i <= n;i++)
scanf("%I64d" ,&v[i]) ;
for(int i = 1;i <= n;i++)
scanf("%I64d" ,&c[i]) ;
while(q--)
{
for(int i = 1;i <= n;i++)
dp[i] = -inf;
__int64 a,b;
scanf("%I64d%I64d" ,&a ,&b) ;
__int64 ma = 0, ma_s = 0, ma_c = 0;
for(int i = 1;i <= n;i++)
{
__int64 temp_b;
__int64 temp_a;
if(dp[c[i]] == -inf)
temp_a = b*v[i];
else
temp_a = a*v[i] + dp[c[i]] ;
if(ma_c == c[i])
{
temp_b = b*v[i] + ma_s;
dp[c[i]] = max(max(dp[c[i]] , temp_b) ,temp_a) ;
ma = max(ma , dp[c[i]]);
}
else
{
temp_b = b*v[i] + ma;
dp[c[i]] = max(max(dp[c[i]] , temp_b),temp_a);
if(dp[c[i]] >= ma)
{
ma_s = ma;
ma_c = c[i] ;
ma = dp[c[i]] ;
}
else ma_s = max(ma_s , dp[c[i]]);
}
}
printf("%I64d\n" , ma) ;
}
}
return 0;
}
Codeforces Round #162 (Div. 1) C Choosing Balls dp
原文：http://blog.csdn.net/cq_pf/article/details/45582977
