HAOI2011 problem a-白红宇

HAOI2011 problem a

阅读量：4350 次

发布时间：2019-06-07

本文共 1048 字，大约阅读时间需要 3 分钟。

题目链接：

DP问题。

考虑一个弱化版——如果没有成绩可能相同的限制，我们应该可以用网络流水部分分？也就是把成绩分成N档，每个点都向自己的合法区间连一条边，然后跑最大匹配，最后用总点数减去即可。

虽然这个方法过不去，但是也给我们一些提示——就是我们可以把对每个点的成绩限制转化为——对应一个可行区间。但是这样显然是不行的，因为成绩有可能相同。所以我们转化一下，不把区间表示成成绩档次，而是设这个区间里有对应区间长度的人数，大家的成绩都相等，然后有ai个人成绩比他高,bi个人比他成绩低。（因为我们并不关心成绩比他高或者低的人他们的成绩是否相等，只要人数够了就行）

我们设\(dp[r]\)表示在区间[1,r]之间，最大的合法数量。

转移方程为dp[r]=max(dp[r],dp[l-1]+min(对应的区间为[l,r]的人数,r-l+1))

update:没有限制还用什么网络流啊哈哈哈，我太智障了，没有限制不就是一个入门难度的题嘛。。。。。

代码如下：

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         #include
          
           #define MAXN 1000010using namespace std;int n,ans;int dp[MAXN];map
           
            
             ,int>m;vector
             
              to[MAXN];int main(){ #ifndef ONLINE_JUDGE freopen("ce.in","r",stdin); #endif scanf("%d",&n); for(int i=1;i<=n;i++) { int a,b,l,r; scanf("%d%d",&a,&b); l=b+1,r=n-a; if(l>r) {continue;} if(m[make_pair(l,r)]==0) to[r].push_back(l); m[make_pair(l,r)]++; } for(int r=1;r<=n;r++) { dp[r]=max(dp[r],dp[r-1]); for(int j=0;j

转载于:https://www.cnblogs.com/fengxunling/p/10367921.html

你可能感兴趣的文章