# 2 条题解

• @ 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 ;
}

• @ 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

(无)

48

41

85%

2