话不多说#xff0c;直接看题甚是想念最近一直在看过河这道题感觉最近脑子有点宕机QAQ现在算是有点懂了打算记录下这道又爱又恨的题。

如有错误欢迎大佬帮忙指出

话不多说直接看题

转移方程为f[i][j]f[i-1][j-x1^2]||f[i-1][j-x2^2]||....||f[i-1][j-xi^2]

现在我们考虑优化一下

因为f[i][j]为bool类型我们可以尝试用bitset优化一下。

我们每一行用bitset,然后用位运算实现比正常平移优化约32倍

f[i]f[i-1]||f[i-1](x[i]^2);(注意bitset最低位在最右边

下面为AC代码

kl;kr;k){f[i]|f[i-1](k*k);}}coutf[n].count();

类似爬楼梯我们记f[i]为到i时最少踩的个数。

如果f[i]上有石子那么f[i]min(f[i-j])1(jsjt).然后一看范围空间与时间都不允许。

我们应该还记得上次背包用map存的情况这是因为空间上有大量的冗余。

而在这一题上我们发现相比于桥石子特别小也说明他们间的距离非常大.

首先按照上述过程我们顺利过了30我们不妨先用自己测试输出一下具体的样子。

我们发现如果两个石子距离十分大从某一个位置开始dp的值都一样。

比赛时直接压缩成一个不超范围的直接提交如果是我的话就直接赋一个2024

当然虽然规律很明显但对于有”强迫症“的我来说还是有点难以接受于是我们从感性与严格证明的角度来论证正确性。

很显然越到后面每一段逐渐重合然后就连续了因为没有石子假设某一段的dp值不同假设有3个不同的值那么到了后面对于每一个点他的状态势必是在3个的不同的值里选min的而3个不同的值中势必有最小的一个越到后面除了最小的其他2个一定会在过程中慢慢被舍弃最终收敛于最小的值当然可能有无法到达的。

总结一下当两个石子离得比较远那在中间的这一段其实就是在经过上一个石子的更新后去不断地筛选出min然后就不变了而我们要做的就是把不变的一段删掉

首先我们得知道一个结论

在离一点oS(S−1)的位置其每一点都可以到并且他们的dp值都一样。

如果两个石子距离s(s-1),那么就把他变成s(s-1)这样就可以顺利通过了注意虽然这样石子后面的几个位置可能不准确但是不妨碍求min的正确性保险一点可以再多空格这样子每一个点的dp都是对的了。

identity来证我在这采用比较直观的方法这里证s^2比较粗略

#includebits/stdc.h

l,s,t,m,ck[110],dp[100000],ze[110];

mapint,int

main(){cinlstm;memset(dp,0x3f,sizeof(dp));for(int

i1;im;i)

i1;im;i){ze[i]min(mm,ck[i]-ck[i-1])ze[i-1];mp[ze[i]]1;}ze[m1]min(mm,l-ck[m])ze[m];dp[0]0;for(int

js;jt;j){if(i-j0){if(mp.count(i)1)

ans1000;for(int