做海报 画册的素材网站,西安seo整站优化,微信跳转链接生成器免费,完本小说做多的网站解析
比较妙的一道题
首先的一个技巧是把一条线段拆成左和右两个端点 顺便也就有了离散化 利用k的关键限制#xff0c;压缩每个点覆盖线段的状态 需要动态更新每一位所对应的线段是哪条
代码
#includebits/stdc.h
using namespace std;
#define ll long long
cons…解析
比较妙的一道题
首先的一个技巧是把一条线段拆成左和右两个端点 顺便也就有了离散化 利用k的关键限制压缩每个点覆盖线段的状态 需要动态更新每一位所对应的线段是哪条
代码
#includebits/stdc.h
using namespace std;
#define ll long long
const int N2e5100;
const int mod2009;
ll read(){ll x0,f1;char cgetchar();while(!isdigit(c)){if(c-)f-1;cgetchar();}while(isdigit(c)){xx*10(c^48);cgetchar();}return x*f;
}
inline void Max(int x,int y){if(xy) xy;}
int n,m,k;
int bit[260],mi[9];
int dp[N][260],tot;
struct node{int pl,op,id;
}p[N];
bool cmp (node a,node b){if(a.pl!b.pl) return a.plb.pl;else return a.opb.op;
}
int nam[9];
int main(){#ifndef ONLINE_JUDGEfreopen(a.in,r,stdin);freopen(a.out,w,stdout);#endifnread();mread();kread();mi[0]1;for(int i1;ik;i) mi[i]mi[i-1]1;for(int i1;imi[k];i) bit[i]bit[i-(i-i)]1;for(int i1;in;i){int lread(),rread();p[tot](node){l,1,i};p[tot](node){r1,-1,i};}sort(p1,p1tot,cmp);memset(dp,-0x3f,sizeof(dp));memset(nam,-1,sizeof(nam));dp[0][0]0;p[tot1].plp[tot].pl;for(int i1;itot;i){if(p[i].op1){int o(-1);for(int j0;jk;j){if(nam[j]-1){nam[j]p[i].id;oj;break;}}//assert(o!-1);//printf(i%d id%d\n,p[i].id,o);for(int s0;smi[k];s){if(smi[o]) continue;Max(dp[i][s],dp[i-1][s](bit[s]1)*(p[i1].pl-p[i].pl));Max(dp[i][s|mi[o]],dp[i-1][s](bit[s|mi[o]]1)*(p[i1].pl-p[i].pl));}}else{int o(-1);for(int j0;jk;j){if(nam[j]p[i].id){nam[j]-1;oj;break;}}for(int s0;smi[k];s){if(smi[o]) Max(dp[i][s-mi[o]],dp[i-1][s](bit[s^mi[o]]1)*(p[i1].pl-p[i].pl));else Max(dp[i][s],dp[i-1][s](bit[s]1)*(p[i1].pl-p[i].pl));}}//printf(\ni%d pl%d id%d op%d\n,i,p[i].pl,p[i].id,p[i].op);//for(int s0;smi[k];s) printf( s%d dp%d\n,s,dp[i][s]);}//fprintf(stderr,check%d\n,dp[4][6]);printf(%d\n,dp[tot][0]);
}
/*
3 50000
013
002
001
*/
