题目链接
https://codeforces.com/problemset/problem/505/C
题目描述
首先 这样的题目可以想到搜索和普通线性dp 但是搜索的话时间复杂度到了1e12了(应该没错)
而正常dp[i][j] 走到i的时候是上一步距离为j的情况下获得宝石的最大值
可是 i ,j<= 30001这样的构造数组f[i][j]必然是爆空间 且会T
那么要怎么解决这个问题呢
偏移量优化
想优化掉一维是不现实的 这个时候可以发现第一步走的距离是d 如果有(d + 1) + (d + 2) + (d + 3) +.... + (d + maxn) <= 30000 考虑k的极端情况maxn也不会超过250
同理(d - 1) + (d - 2) + (d - 3) + .... + (d - minn) <= 30000 minn 不会小于 -250
真是距离 = j + d - 250
//偏移量j 相对与原 d 的变化咯
可以写出关键代码
for(int i =1; i <= 30001; i ++)
{
for(int j = 1; j <= 600;j ++)
{
int len = j - 250 + d;
if(i - len <= 0 || len <= 0)continue;
int res = max(f[i - len][j],max(f[i - len][j + 1],f[i - len][j - 1]));
if(res != -1)
{
f[i][j] = max(f[i][j],res + mp[i]);
ans = max(ans,f[i][j]);
}
}
}
ac代码
include
include
include
using namespace std;
const int N = 3e4 + 10;
int f[N][600];//走到i时 上一步走的是 j + d - 250;
int mp[N];
int n,d;
int main()
{
cin >> n >> d;
for(int i = 1; i <= n; i ++){
int x;
cin >> x;
mp[x] ++;
}
memset(f,-1,sizeof f);
int ans= 0;
f[d][d - d + 250] = mp[d];//因为第一步是d所以 j + d - 250 == d
ans = mp[d];//防止特殊情况比如 1 30000 30000 会直接在特判中跳出循环
for(int i =1; i <= 30001; i ++)
{
for(int j = 1; j <= 600;j ++)
{
// if(f[i][j] == -1)
// continue;
int len = j - 250 + d;
if(i - len <= 0 || len <= 0)continue;
int res = max(f[i - len][j],max(f[i - len][j + 1],f[i - len][j - 1]));
if(res != -1)
{
f[i][j] = max(f[i][j],res + mp[i]);
ans = max(ans,f[i][j]);
}
//
}//cout << "?";
}
cout << ans;
return 0;
}