民治做网站哪家便宜,网站维护要学多久,wordpress_zh,51外链代发网好久不见#xff0c;甚是想念#xff0c;最近一直在看过河这道题#xff08;感觉最近脑子有点宕机QAQ#xff09;#xff0c;现在算是有点懂了#xff0c;打算记录下这道又爱又恨的题。#xff08;如有错误欢迎大佬帮忙指出#xff09;
话不多说#xff0c;直接看题甚是想念最近一直在看过河这道题感觉最近脑子有点宕机QAQ现在算是有点懂了打算记录下这道又爱又恨的题。如有错误欢迎大佬帮忙指出
话不多说直接看题 类比分组背包我们可以令f[i][j]表示前i个数能否组成j.
转移方程为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代码
#includebits/stdc.h
using namespace std;
int n;
bitset1000100 f[110];
int main(){cinn;f[0][0]1;for(int i1;in;i){int l,r;scanf(%d%d,l,r);for(int 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存的情况这是因为空间上有大量的冗余。
而在这一题上我们发现相比于桥石子特别小也说明他们间的距离非常大.
于是我们进行状态压缩。
从这开始就困了我蛮久还是自己太菜了QAQ
首先按照上述过程我们顺利过了30我们不妨先用自己测试输出一下具体的样子。 我们发现如果两个石子距离十分大从某一个位置开始dp的值都一样。
比赛时直接压缩成一个不超范围的直接提交如果是我的话就直接赋一个2024
当然虽然规律很明显但对于有”强迫症“的我来说还是有点难以接受于是我们从感性与严格证明的角度来论证正确性。
我们不妨自己先画个数轴我们以6/7举例。 很显然越到后面每一段逐渐重合然后就连续了因为没有石子假设某一段的dp值不同假设有3个不同的值那么到了后面对于每一个点他的状态势必是在3个的不同的值里选min的而3个不同的值中势必有最小的一个越到后面除了最小的其他2个一定会在过程中慢慢被舍弃最终收敛于最小的值当然可能有无法到达的。
总结一下当两个石子离得比较远那在中间的这一段其实就是在经过上一个石子的更新后去不断地筛选出min然后就不变了而我们要做的就是把不变的一段删掉
可能有点抽象那么我们来严格证一下
首先我们得知道一个结论
在离一点oS(S−1)的位置其每一点都可以到等会证
然后请看分析 因此我们推出一个结论
在离一点oS(S−1)的位置其每一点都可以到并且他们的dp值都一样。
接下来我们就得到了压缩方法
如果两个石子距离s(s-1),那么就把他变成s(s-1)这样就可以顺利通过了注意虽然这样石子后面的几个位置可能不准确但是不妨碍求min的正确性保险一点可以再多空格这样子每一个点的dp都是对的了。
下面是对那个数学结论的证明
我看网上很多是用Bezouts identity来证我在这采用比较直观的方法这里证s^2比较粗略 下面给出AC代码注意st的情况
#includebits/stdc.h
using namespace std;
int l,s,t,m,ck[110],dp[100000],ze[110];
mapint,int mp;
bool cmp(int a,int b){return ab;
}
int main(){cinlstm;memset(dp,0x3f,sizeof(dp));for(int i1;im;i) scanf(%d,ck[i]);if(st){int cnt0;for(int i1;im;i){if(ck[i]%s0) cnt;}coutcnt;return 0;}sort(ck1,ckm1,cmp);int mms*s10;ze[0]0;for(int 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 i1;ize[m1]t-1;i){for(int js;jt;j){if(i-j0){if(mp.count(i)1) dp[i]min(dp[i],1dp[i-j]);else dp[i]min(dp[i],dp[i-j]);}}}int ans1000;for(int ize[m1];ize[m1]t-1;i) ansmin(ans,dp[i]);coutans;
}
