题解

2 条题解

  • 0
    @ 2014-07-04 23:06:44

    #include <cstdio>
    #include <algorithm>
    #include <cstring>

    using namespace std ;

    const int inf = 100000000 ;
    const int maxn = 210 ;

    int a[ maxn << 1 ] , b[ maxn << 1 ] , an , bn ;

    inline int getp( int x ) {
    if ( x == b[ 1 ] ) return 1 ;
    if ( x == b[ bn ] ) return bn ;
    int l = 1 , r = bn , mid ;
    while ( r - l > 1 ) {
    mid = ( l + r ) >> 1 ;
    if ( b[ mid ] == x ) return mid ;
    if ( x < b[ mid ] ) r = mid ; else l = mid ;
    }
    }

    int n , S[ maxn ] , T[ maxn ] , num[ maxn << 1 ][ maxn << 1 ] , pre[ maxn << 1 ][ maxn ] , suff[ maxn << 1 ][ maxn ] , ans[ maxn << 1 ][ maxn << 1 ] ;

    #define cal( i , j , x , y ) ( min( num[ i ][ j ] + x + y , pre[ i ][ x ] + suff[ j ][ y ] ) )

    int main( ) {
    scanf( "%d" , &n ) ; an = 0 ;
    for ( int i = 0 ; i ++ < n ; ) {
    scanf( "%d%d" , S + i , T + i ) ; T[ i ] += S[ i ] ;
    a[ ++ an ] = S[ i ] , a[ ++ an ] = T[ i ] ;
    }
    sort( a + 1 , a + an + 1 ) ;
    bn = 0 ;
    for ( int i = 0 ; i ++ < an ; ) if ( i == 1 || a[ i ] != a[ i - 1 ] ) b[ ++ bn ] = a[ i ] ;
    for ( int i = 0 ; i ++ < n ; ) {
    S[ i ] = getp( S[ i ] ) , T[ i ] = getp( T[ i ] ) ;
    }
    for ( int i = 0 ; i ++ < bn ; ) for ( int j = i ; j ++ < bn ; ) {
    num[ i ][ j ] = 0 ;
    for ( int k = 0 ; k ++ < n ; ) if ( S[ k ] >= i && T[ k ] <= j ) ++ num[ i ][ j ] ;
    }
    for ( int i = 0 ; i ++ < bn ; ) for ( int j = 0 ; j <= n ; ++ j ) pre[ i ][ j ] = suff[ i ][ j ] = - inf ;
    pre[ 1 ][ 0 ] = 0 ;
    for ( int i = 2 ; i <= bn ; ++ i ) for ( int j = 0 ; j <= num[ 1 ][ i ] ; ++ j ) for ( int k = 0 ; k < i ; ++ k ) {
    pre[ i ][ j ] = max( pre[ i ][ j ] , pre[ k ][ j ] + num[ k ][ i ] ) ;
    if ( j >= num[ k ][ i ] ) pre[ i ][ j ] = max( pre[ i ][ j ] , pre[ k ][ j - num[ k ][ i ] ] ) ;
    }
    suff[ bn ][ 0 ] = 0 ;
    for ( int i = bn - 1 ; i ; -- i ) for ( int j = 0 ; j <= num[ i ][ bn ] ; ++ j ) for ( int k = bn ; k > i ; -- k ) {
    suff[ i ][ j ] = max( suff[ i ][ j ] , suff[ k ][ j ] + num[ i ][ k ] ) ;
    if ( j >= num[ i ][ k ] ) suff[ i ][ j ] = max( suff[ i ][ j ] , suff[ k ][ j - num[ i ][ k ] ] ) ;
    }
    int Ans = 0 ;
    for ( int i = 0 ; i ++ < bn ; ) for ( int j = i ; j ++ < bn ; ) {
    ans[ i ][ j ] = - inf ;
    int y = num[ j ][ bn ] ;
    for ( int x = 0 ; x <= num[ 1 ][ i ] ; ++ x ) {
    for ( ; y && cal( i , j , x , y - 1 ) >= cal( i , j , x , y ) ; -- y ) ;
    ans[ i ][ j ] = max( ans[ i ][ j ] , cal( i , j , x , y ) ) ;
    }
    Ans = max( Ans , ans[ i ][ j ] ) ;
    }
    printf( "%d\n" , Ans ) ;
    for ( int k = 0 ; k ++ < n ; ) {
    Ans = 0 ;
    for ( int i = 0 ; i ++ < S[ k ] ; ) for ( int j = T[ k ] ; j <= bn ; ++ j ) {
    Ans = max( Ans , ans[ i ][ j ] ) ;
    }
    printf( "%d\n" , Ans ) ;
    }
    return 0 ;
    }

  • 0
    @ 2014-02-06 19:27:30

    #include<iostream>
    #include<cstdio>
    #include<cmath>
    #include<cstring>
    #include<map>
    #include<algorithm>
    using namespace std;
    #define MAXN 210
    pair<int,int> event[MAXN];
    int num[MAXN*2][MAXN*2],pre[2*MAXN][MAXN],back[2*MAXN][MAXN],ans[2*MAXN][2*MAXN];
    int a[MAXN*2];
    map<int,int> home;
    int n,m;
    void discretization()
    {
    sort(a+1,a+2*n+1);
    int i,j=0;
    a[0]=-1;
    for(i=1;i<=2*n;i++)
    {
    if(a[i]!=a[i-1])
    j++;
    home[a[i]]=j;
    }
    for(i=1;i<=n;i++)
    {
    event[i].first=home[event[i].first];
    event[i].second=home[event[i].second];
    //cout<<event[i].first<<" "<<event[i].second<<endl;
    }
    m=j;
    }
    void solve_all()
    {
    int i,j,k;
    memset(num,0,sizeof(num));
    memset(pre,0xaf,sizeof(pre));
    memset(back,0xaf,sizeof(back));
    //cout<<pre[0][0]<<endl;
    int ans=0;
    pre[0][0]=0;
    for(k=1;k<=n;k++)
    for(i=0;i<=event[k].first;i++)
    for(j=event[k].second;j<=m+1;j++)
    num[i][j]++;

    for(i=1;i<=m;i++)
    for(j=0;j<=n;j++)
    {
    for(k=0;k<i;k++)
    {
    pre[i][j]=max(pre[i][j],pre[k][j]+num[k][i]);
    if(j>=num[k][i])
    pre[i][j]=max(pre[i][j],pre[k][j-num[k][i]]);
    }
    //cout<<i<<" "<<j<<" "<<pre[i][j]<<endl;
    }
    back[m+1][0]=0;
    for(i=m;i>=1;i--)
    for(j=0;j<=n;j++)
    {
    for(k=i+1;k<=m+1;k++)
    {
    back[i][j]=max(back[i][j],back[k][j]+num[i][k]);
    if(j>=num[i][k])
    back[i][j]=max(back[i][j],back[k][j-num[i][k]]);
    }
    //cout<<i<<" "<<j<<" "<<back[i][j]<<endl;
    }
    for(j=0;j<=n;j++)
    ans=max(ans,min(j,pre[m][j]));
    printf("%d\n",ans);
    }
    int calc(int i,int j,int x,int y)
    {
    return min(x+y+num[i][j],pre[i][x]+back[j][y]);
    }
    void solve_part()
    {
    int i,j,x,y,k;
    memset(ans,0,sizeof(ans));
    int s=0;
    for(i=1;i<=m;i++)
    for(j=i;j<=m;j++)
    {
    y=n;
    s=0;
    for(x=0;x<=n;x++)
    {
    for(y;y>0;y--)
    {
    if(calc(i,j,x,y-1)<calc(i,j,x,y))
    break;
    }
    s=max(s,calc(i,j,x,y));
    }
    ans[i][j]=s;
    }
    for(k=1;k<=n;k++)
    {
    s=0;
    for(i=1;i<=event[k].first;i++)
    for(j=event[k].second;j<=m;j++)
    s=max(s,ans[i][j]);
    printf("%d\n",s);
    }
    }

    int main()
    {
    scanf("%d",&n);
    int i;
    for(i=1;i<=n;i++)
    {
    scanf("%d%d",&event[i].first,&event[i].second);
    event[i].second+=event[i].first;
    a[2*i-1]=event[i].first; a[2*i]=event[i].second;
    }
    discretization();
    solve_all();
    solve_part();
    return 0;
    }

  • 1

信息

ID
1818
难度
1
分类
(无)
标签
递交数
46
已通过
39
通过率
85%
被复制
1
上传者