网站 网安备案,电子商务网站建设 教材,福建省建住房建设部网站,海外电商能赚钱吗CF559E Gerald and Path 设 \(dp(i,p)\) 表示完成前 \(i\) 条线段的覆盖#xff0c;最右端位于 \(p\) 点的最大收益。 转移#xff1f;向下一条线段转移时加上他们中间的距离#xff1f;发现这样没有办法统计 \(p\) 点以前的空位了#xff01; \(\color{yellow}{\bigstar\t… CF559E Gerald and Path 设 \(dp(i,p)\) 表示完成前 \(i\) 条线段的覆盖最右端位于 \(p\) 点的最大收益。 转移向下一条线段转移时加上他们中间的距离发现这样没有办法统计 \(p\) 点以前的空位了 \(\color{yellow}{\bigstar\texttt{Trick}}\)如果出现上面没有办法统计 \(p\) 点以前的空位的情况说明覆盖 \(p\) 点的这条线段是没有用的每次只需要考虑有用的线段。 若要枚举有用的线段从 \(i\) 点枚举下一个有用的线段 \(k\)钦定 \([i1,k-1]\) 之间的线段都是没有用的这样就可以像上面一样转移了。 但是如果没有用的线段中出现一个线段它的右端点超过了 \(k\) 线段的右端点呢那就再扫过 \([i1,k-1]\) 线段的时候统计下最右边端再加上它与 \(k\) 线段右端的贡献即可。 实现的时候记 \(p\) 点只用记录最右端线段编号和朝向即可设 \(dp(i,j,p)\) 表示到 \(i\) 线段为止最右边的线段是 \(j\)它的朝向为 \(p\) 的最大收益。 \[dp(k,x,y)\leftarrow dp(i,j,p)\min(r_k-p,len_k)r_x-r_k \]#define Maxn 105
int n,ans;
int dp[Maxn][Maxn][2];
struct Seg
{int pos,len;Seg(int Pos0,int Len0):pos(Pos),len(Len){}inline bool friend operator (Seg x,Seg y) { return x.posy.pos; }
}s[Maxn];
int main()
{nrd();for(int i1,p,l;in;i) prd(),lrd(),s[i]Seg(p,l);sort(s1,sn1),s[0].pos-inf;for(int i0;in;i)for(int j0;ji;j) for(int p0;p2;p){int rns[j].posp*s[j].len,maxx-inf,pos-1,d;ansmax(ans,dp[i][j][p]);for(int ki1;kn;k) for(int q0;q2;q){int curs[k].posq*s[k].len;if(curmaxx) maxxcur,posk,dq;dp[k][pos][d]max(dp[k][pos][d],dp[i][j][p]min(cur-rn,s[k].len)maxx-cur);}}printf(%d\n,ans);return 0;
}
