NC228152. 秘密构成
描述
承载着70亿的秘密
小小的行星，没有办法呼吸
人类的正义和人类的数量一样多的吧
两个人化作同一个秘密吧
给出 个二元组
。在其中删除若干个二元组，剩下的二元组中相邻的位置
和
会产生价值定义为
其中 为一个函数，定义为
。
求最大能得到的价值和。
输入描述
第一行输入三个整数
表示二元组数量和函数
的系数
第二行输入
个整数，第
个为
。
第三行输入
。
输出描述
输出包括一行一个整数表示最大价值和。
示例1
输入:
5 0 1 1 2 3 4 5 2 1 4 2 4
输出:
6
说明:
选择最后两个二元组 (4,2) , (5,4) 则能够获得 6 的价值。示例2
输入:
5 2 0 1 2 3 4 5 2 1 4 2 4
输出:
312
C++ 解法, 执行用时: 317ms, 内存消耗: 3980K, 提交时间: 2021-11-03 22:54:09
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll i,j,k,n,m,t,x,y,f[505][505],res,tmp,nmsl1[666666],nmsl2[666666],a,b;
ll h(ll x){
return a*(x%100)*(x%100)+b*x;
}
int main(){
memset(f,150,sizeof(f));
cin.tie(0);
cin>>t>>a>>b;
for(i=1;i<=t;i++)cin>>nmsl1[i];
for(i=1;i<=t;i++)cin>>nmsl2[i];
for(j=1;j<=t;j++){
x=nmsl1[j];y=nmsl2[j];
tmp=0;
for(i=1;i<=500;i++){
tmp=max(tmp,f[i][x]+h(y*i));
}
res=max(res,tmp);
for(i=1;i<=500;i++){
f[x][i]=max(f[x][i],tmp-h(y*i));
}
}
cout<<res;
}