流程做网站,延庆宜昌网站建设,学勇建站,如何在百度上建免费网站题目传送门
引
复杂度没算对导致不敢写#xff0c;分析复杂度时还是多考虑势能#xff0c;不然错过正解就亏了
解法
操作一可以一开始就做了 考虑状压 m a s k mask mask 是已加入序列的元素 转移枚举一段连续的区间即可 复杂度乍眼一看是 O ( n 2 2 n ) O(n^22^n) O(…题目传送门
引
复杂度没算对导致不敢写分析复杂度时还是多考虑势能不然错过正解就亏了
解法
操作一可以一开始就做了 考虑状压 m a s k mask mask 是已加入序列的元素 转移枚举一段连续的区间即可 复杂度乍眼一看是 O ( n 2 2 n ) O(n^22^n) O(n22n) 的 注意一个长度为 k k k 的区间会被转移 2 n − k 2^{n-k} 2n−k 次 复杂度就为 O ( ∑ i 1 n i ∗ ( n − i 1 ) ∗ 2 n − k ) ≈ O ( n 2 n ) O(\sum_{i1}^{n}i*(n-i1)*2^{n-k}) \approx O(n2^n) O(∑i1ni∗(n−i1)∗2n−k)≈O(n2n)
Code
#include algorithm
#include iostream
#include cstring
#include vector
#include queueusing ll long long ;
using namespace std;const int N25,M(122)7;int n;
ll a[N],b[N],c;
ll f[M];void work(int mask) {int ba__builtin_popcount(mask);for(int i1;in;i) if(!(mask(i-1)1)) {int ji;while(jn !(maskj1)) j;for(int li;lj;l) {ll sum0; int S0;for(int rl;rj;r) {S|(1(r-1));sumabs(b[r]-a[bar-l1]);f[mask|S]min(f[mask|S],f[mask]csum);}}ij;}
}int main(){scanf(%d %lld,n,c);for(int i1;in;i) scanf(%lld,a[i]);for(int i1;in;i) scanf(%lld,b[i]);for(int i1;i(1n);i) f[i]1e18;f[0]-c;for(int i0;i(1n)-1;i) {work(i);}printf(%lld\n,f[(1n)-1]);
}
