和目网站,廉江市住房和城乡规划建设局网站,兰州北京网站建设,吴忠市建设网站CF1497D Genius
题意#xff1a;
n个问题从i到n编号#xff0c;第i个问题给出的ci2i,tagi,sic_i2^i,tag_i,s_ici2i,tagi,si 解决问题i后解决问题j条件是#xff1a;IQ|ci−cjc_i-c_jci−cj|,同时获得|si−sjs_i-s_jsi−sj|分 问题解决得次数和顺序不受限…CF1497D Genius
题意
n个问题从i到n编号第i个问题给出的ci2i,tagi,sic_i2^i,tag_i,s_ici2i,tagi,si 解决问题i后解决问题j条件是IQ|ci−cjc_i-c_jci−cj|,同时获得|si−sjs_i-s_jsi−sj|分 问题解决得次数和顺序不受限制 一开始IQ0求最高可获得得分数 内存限制31.25MB大致可以开1e7的数组
题解
很明显动态规划按照一般思路设dp[i][j]上一次是第i个问题本次是第j个问题的最大贡献。但是很明显空间不够 对于dp[][]的状态转移当且仅当∣ck−cj∣∣ci−cj∣|c_k-c_j||c_i-c_j|∣ck−cj∣∣ci−cj∣,可以从dpi,jdp_{i,j}dpi,j转移到dpj,kdp_{j,k}dpj,k 我们将这个∣ci−cj∣|c_i-c_j|∣ci−cj∣放在图论上分析就是有n个点任意两点之间建边边权为∣ci−cj∣|c_i-c_j|∣ci−cj∣的一个无向图我们可以在无向图商从小边权向大边权转移这样就可以不用二维来转移降低空间复杂度 设dpidp_idpi表示最后一个问题是i的最大贡献当我们走(i,j)这条边时状态i可以由状态j更新同理状态j也可以由状态i更新因为这是无向边。 有转移方程 val∣si,sj∣val|s_i,s_j|val∣si,sj∣ tmpidpitmp_idp_itmpidpi tmpjdpjtmp_jdp_jtmpjdpj dpimax(dpi,tmpjval)dp_imax(dp_i,tmp_jval)dpimax(dpi,tmpjval) dpjmax(dpj,tmpival)dp_jmax(dp_j,tmp_ival)dpjmax(dpj,tmpival) 不过问题还没完全解决现在我们还要考虑几个问题
边权一样优先级顺序如何按照边权从小到大枚举边
因为ci2ic_i2^ici2i,边权都是∣2i−2j∣|2^i-2^j|∣2i−2j∣的形式说明对于任意不同的(i,j)所对应的边也一定不同。也就是不会有边权一样的边 对于第二个问题因为有空间的限制我们不可以存下所有边然后排序。此时我们观察(i,j)权值的变化情况假设ij权值二进制状态下区间[i,j-1]的位置都是1说明当j越大时权值越大当j一样时i越小权值越大 那么我们就看这样枚举点对(i,j),先枚举j从小到大然后枚举i从大到小这样枚举出来的边权保证从小到大
代码
#include bits/stdc.h
#include unordered_map
#define debug(a, b) printf(%s %d\n, a, b);
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pairint, int PII;
clock_t startTime, endTime;
//Fe~Jozky
const ll INF_ll 1e18;
const int INF_int 0x3f3f3f3f;
void read(){};
template typename _Tp, typename... _Tps void read(_Tp x, _Tps... Ar)
{x 0;char c getchar();bool flag 0;while (c 0 || c 9)flag| (c -), c getchar();while (c 0 c 9)x (x 3) (x 1) (c ^ 48), c getchar();if (flag)x -x;read(Ar...);
}
template typename T inline void write(T x)
{if (x 0) {x ~(x - 1);putchar(-);}if (x 9)write(x / 10);putchar(x % 10 0);
}
void rd_test()
{
#ifdef ONLINE_JUDGE
#elsestartTime clock();freopen(data.in, r, stdin);
#endif
}
void Time_test()
{
#ifdef ONLINE_JUDGE
#elseendTime clock();printf(\nRun Time:%lfs\n, (double)(endTime - startTime) / CLOCKS_PER_SEC);
#endif
}
const int maxn 5e3 9;
ll tag[maxn];
ll s[maxn];
ll dp[maxn];
int x[maxn][maxn];
int main()
{//rd_test();int t;read(t);while (t--) {int n;cin n;memset(dp, 0, sizeof(dp));for (int i 1; i n; i)cin tag[i];for (int i 1; i n; i)cin s[i];for (int j 2; j n; j) {for (int i j - 1; i 1; i--) {if (tag[i] tag[j])continue;ll tmpi dp[i];ll tmpj dp[j];ll val abs(s[i] - s[j]);dp[i] max(dp[i], tmpj val);dp[j] max(dp[j], tmpi val);}}ll maxx 0;for (int i 1; i n; i) {maxx max(maxx, dp[i]);}cout maxx endl;}//Time_test();
}
