DP水题大礼包
一天8题，6道水题
birthday
做法一：考虑在完全背包上加点东西
做法二：在完全背包第一次转移时加值
chess
就是个状压DP模板
#include<bits/stdc++.h>
using namespace std ;
inline int read(){
int s=0 ; char g=getchar() ; while(g>'9'||g<'0')g=getchar() ;
while(g>='0'&&g<='9')s=s*10+g-'0',g=getchar() ; return s ;
}
int N , M , state[ 4096 ] , field[ 13 ] , mod = 100000000 , dp[ 13 ][ 4096 ] ;
int main(){
freopen("chess.in","r",stdin);
freopen("chess.out","w",stdout);
N = read() , M = read() ; int m1 ;
for( int i = 1 ; i <= N ; ++i )
for( int j = 1 ; j <= M ; ++j )
m1 = read() , field[ i ] = ( field[ i ]<<1 ) + (m1^1) ;
for( int i = 0 ; i < ( 1<<M ) ; ++i )state[ i ] = ( ( !( (i<<1)&i) )&&( !(i&(i>>1) )) ) ;
dp[ 0 ][ 0 ] = 1 ;
for( int i = 1 ; i <= N ; ++i )
for( int j = 0 ; j < (1<<M) ; ++j ){//枚举状态
if( !state[ j ] )continue ;
if( j&field[ i ] )continue ;
for( int k = 0 ; k < (1<<M) ; ++k ){
if( k&j )continue ;
dp[ i ][ j ] = ( dp[ i-1 ][ k ] + dp[ i ][ j ] )%mod;
}
}
int ans = 0 ;
for( int i = 0 ; i < ( 1<<M ) ; ++i )ans = (dp[ N ][ i ] + ans)%mod;
cout<<ans ;
}
question
悬线法入门题，不懂得请看ssw02的 悬线法总结
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1005 ;
inline int read(){
int s=0 ; char g=getchar() ; while( g>'9'||g<'0' )g=getchar() ;
while( g>='0'&&g<='9')s=s*10+g-'0',g=getchar(); return s ;
}
int N , M , a[ MAXN ][ MAXN ] , flag = 0 ;
int l[ MAXN ][ MAXN ] , r[ MAXN ][ MAXN ] , up[ MAXN ][ MAXN ] , ans = 0 ;
int main(){
freopen("question.in","r",stdin);
freopen("question.out","w",stdout);
N = read() , M = read() ;
for( int i = 1 ; i <= N ; ++i )
for( int j = 1 ; j <= M ; ++j )
a[ i ][ j ] = read() , l[ i ][ j ] = r[ i ][ j ] = j , up[ i ][ j ] = 1 , flag = max(flag,a[i][j]) ;
for( int i = 1 ; i <= N ; ++i )
for( int j = 2 ; j <= M ; ++j )
if( a[i][j] && a[i][j-1] )l[i][j] = l[i][j-1] ;
for( int i = 1 ; i <= N ; ++i )
for( int j = M-1 ; j >= 1 ; --j )
if( a[i][j] && a[i][j+1] )r[i][j] = r[i][j+1] ;
for( int i = 1 ; i <= N ; ++i )
for( int j = 1 ; j <= M ; ++j ){
if( i > 1 )
if( a[i][j] && a[i-1][j] ){
l[i][j] = max( l[i][j] , l[i-1][j] ) ;
r[i][j] = min( r[i][j] , r[i-1][j] ) ;
up[i][j] = up[i-1][j] + 1 ;
}
int lon = r[i][j] - l[i][j] + 1 ;
ans = max( ans , lon*up[i][j] ) ;
}
if( !flag )cout<<0;
else cout<<ans;
}
road
DAG上DP ， 按拓扑排序保证无后效性即可
#include<bits/stdc++.h>
using namespace std ;
const int MAXN = 100005 ;
#define ll long long
inline int read(){
int s=0,w=1 ; char g=getchar() ; while(g>'9'||g<'0'){if(g=='-')w=-1;g=getchar();} ;
while(g>='0'&&g<='9')s=s*10+g-'0',g=getchar() ; return s*w ;
}
int N , M , tot = 1 , head[ MAXN ] , to[ MAXN*20 ] , nex[ MAXN*20 ] , a[ MAXN ] , du[ MAXN ] , ru[ MAXN ] ;
ll dis[ MAXN ] ;
bool vis[ MAXN ] ;
queue<int>q ;
void add( int x , int y ){
to[ ++tot ] = y , nex[ tot ] = head[ x ] , head[ x ] = tot ;
}
void toposort(){
while( !q.empty() ){
int u = q.front() ; q.pop() ; vis[ u ] = false ;
for( int i = head[ u ] ; i ; i = nex[ i ] ){
dis[ to[i] ] = max( dis[ u ]+(ll)a[ to[i] ] , dis[ to[i] ] ) ;
du[ to[i] ]-- ;
if( du[ to[i] ]==0 && vis[ to[i] ]==0 ){
q.push( to[i] ) ; vis[ to[i] ] = true ;
}
}
}
}
int main(){
freopen("road.in","r",stdin);
freopen("road.out","w",stdout);
N = read() , M = read() ; int m1 , m2 ;
for( int i = 1 ; i <= N ; ++i )a[ i ] = read() , dis[ i ] = -2000000005 ;
for( int i = 1 ; i <= M ; ++i ){
m1 = read() , m2 = read() , du[ m1 ]++ , ru[ m2 ]++ ;
add( m2 , m1 ) ;
}
for( int i = 1 ; i <= N ; ++i )
if( !du[ i ] ){
vis[ i ] = true , dis[ i ] = (ll)a[ i ] ; q.push( i ) ;
}
toposort() ;
ll ans = -2000000005 ;
for( int i = 1 ; i <= N ; ++i )
if( !ru[ i ] )
ans = max( ans , dis[ i ] ) ;
cout<<ans ;
}
Gray
我们考虑到，每一位的影响只和当前位置的字符和先前一位的字符有关，然后就是分情况的线性DP
#include<bits/stdc++.h>
using namespace std ;
#define ll long long
inline ll read(){
ll s=0,w=1 ; char g=getchar() ; while(g>'9'||g<'0'){if(g=='-')w=-1;g=getchar();}
while(g>='0'&&g<='9')s=s*10+g-'0',g=getchar() ; return s*w ;
}
char s[ 200005 ] ;
ll N , val[ 200005 ] , dp[ 200005 ][ 2 ] ;
inline ll max( ll x , ll y ){
if( x > y )return x ;
else return y ;
}
void updata( int i , int x ){
if( x ){
if( dp[ i-1 ][ 0 ] != -1 )dp[ i ][ 1 ] = dp[ i-1 ][ 0 ] + val[ i ] ;
if( dp[ i-1 ][ 1 ] != -1 )dp[ i ][ 1 ] = max( dp[ i ][ 1 ] , dp[ i-1 ][ 1 ] ) ;
return ;
}
if( dp[ i-1 ][ 1 ] != -1 )dp[ i ][ 0 ] = dp[ i-1 ][ 1 ] + val[ i ] ;
if( dp[ i-1 ][ 0 ] != -1 )dp[ i ][ 0 ] = max( dp[ i ][ 0 ] , dp[ i-1 ][ 0 ] ) ;
}
int main(){
freopen("gray.in","r",stdin);
freopen("gray.out","w",stdout);
scanf("%s",s) ;
N = strlen(s) ; dp[ 0 ][ 1 ] = -1 ;
for( int i = 1 ; i <= N ; ++i )val[ i ] = read() , dp[ i ][ 1 ] = dp[ i ][ 0 ] = -1e10 ;//坑人
for( int i = 1 ; i <= N ; ++i ){
if( s[i-1] == '0' ){
dp[ i ][ 1 ] = -1 ;
updata( i , 0 ) ;
}
else if( s[i-1] == '1' ){
dp[ i ][ 0 ] = -1 ;
updata( i , 1 ) ;
}
else{
updata( i , 0 ) ;
updata( i , 1 ) ;
}
}
cout<<max( dp[ N ][ 1 ] , dp[ N ][ 0 ] ) ;
/*for( int i = 1 ; i <= N ; ++i )cout<<val[ i ]<<" ";cout<<endl ;
for( int i = 1 ; i <= N ; ++i )cout<<dp[ i ][ 0 ]<<" " ;cout<<endl ;
for( int i = 1 ; i <= N ; ++i )cout<<dp[ i ][ 1 ]<<' ' ;*/
return 0 ;
}
number
RMQ问题，线段树或者树状数组或者ST表维护（留个ST表板子）
#include<bits/stdc++.h>
using namespace std ;
const int MAXN = 100005 ;
int N , M , a[ MAXN ] , st[ MAXN ][ 20 ] , log_a[ MAXN ] ;
inline int read(){
int s=0 ,w=1; char g=getchar() ; while(g>'9'||g<'0'){if(g=='-')w=-1;g=getchar();}
while(g>='0'&&g<='9')s=s*10+g-'0',g=getchar() ; return s*w ;
}
void prepare(){
for( int i = 1 ; i <= 17 ; ++i )
for( int u = 1 ; u + (1<<i) - 1 <= N ; ++u )
st[ u ][ i ] = min( st[ u ][ i-1 ] , st[ u + ( 1<<i-1 ) ][ i-1 ] ) ;
}
int ask( int l , int r ){
int k = log_a[ r-l+1 ] ;
return min( st[ l ][ k ] , st[ r-(1<<k)+1 ][ k ] ) ;
}
int main(){
freopen("number.in","r",stdin);
freopen("number.out","w",stdout);
N = read() ; int m1 , m2 ; log_a[0]=-1;
for( int i = 1 ; i <= N ; ++i )st[ i ][ 0 ] = read() , log_a[i]=log_a[ i>>1 ] +1 ;
M = read() ;prepare() ;
for( int i = 1 ; i <= M ; ++i ){
m1 = read() , m2 = read() ;
printf("%d
",ask(m1,m2) ) ;
}
return 0 ;
}
hotel
好题，我们考虑到从每个房间数的人并不好维护，然后考虑到经过的人只能是从左右两个位置进入和出去
具体写代码里了
#include<bits/stdc++.h>
using namespace std ;
#define ll long long
const int MAXN = 1e5+5 ;
inline ll read(){
ll s=0 ; char g=getchar() ; while(g>'9'||g<'0')g=getchar() ;
while( g>='0'&&g<='9')s=s*10+g-'0',g=getchar() ; return s ;
}
ll N , dp[ MAXN ][ 15 ] , a[ MAXN ] ;
inline ll min( ll x , ll y ){
return ( x<y )?x:y ;
}
inline bool check( int x ){
if( x==0||x==4||x==7 )return true ;
else return false ;
}
int main(){// dp[i][0 ~ 14]表示从1~i再向外走出去-7(负数就是进来)~7个人就能使1~i房间合法的最小费用.
freopen("hotel.in","r",stdin);
freopen("hotel.out","w",stdout);
N = read() ;
for( int i = 1 ; i <= N ; ++i )a[ i ] = read() ;
for( int i = 0 ; i <= N ; ++i )
for( int j = 0 ; j <= 14 ; ++j )dp[ i ][ j ] = 1e10 ;
dp[ 0 ][ 7 ] = 0 ;
for( int i = 1 ; i <= N ; ++i )
for( int j = 0 ; j <= 14 ; ++j )
for( int k = 0 ; k <= 14 ; ++k ){
int in = j - 7 , out = k - 7 ;//存在负值 7为基数位
if( check( a[ i ] + in - out ) ){
dp[ i ][ k ] = min( dp[ i ][ k ] , dp[ i-1 ][ j ] + abs(in) ) ;
}
}
cout<<( (dp[ N ][ 7 ]==1e10 )?-1:dp[ N ][ 7 ] ) ;
}
gift
区间DP ， 移项后将 dp[ i ][ k ] - k * val[ i ]丢到单调队列中维护
#include<bits/stdc++.h>
using namespace std ;
const int MAXN = 16005 ;
#define ll long long
inline ll read(){
ll s=0,w=1 ; char g=getchar() ; while(g>'9'||g<'0'){if(g=='-')w=-1;g=getchar();}
while(g>='0'&&g<='9')s=s*10+g-'0',g=getchar() ; return s*w ;
}
ll N , M , ans , dp[ 105 ][ MAXN ] , q[ MAXN ] ;
struct ap{
ll l , val , pre ;
}t[ 105 ] ;
inline bool cmp( ap x , ap y ){
return x.pre < y.pre ;
}
inline ll max( ll x , ll y ){
return ( x > y )?x:y ;
}
int main(){
freopen("gift.in","r",stdin) ;
freopen("gift.out","w",stdout);
N = read() , M = read() ;
for( int i = 1 ; i <= M ; ++i )
t[ i ].l = read() , t[ i ].val = read() , t[ i ].pre = read() ;
sort( t+1 , t+M+1 , cmp ) ;
for( int i = 1 ; i <= M ; ++i ){
int head = 1 , tail = 0 ;
q[ ++tail ] = max( t[ i ].pre - t[ i ].l , 0 ) ;
for(int j = 1; j <= N; ++j ){
dp[i][j] = max( dp[i - 1][j], dp[i][j - 1] ) ;//不放
if( j >= t[ i ].pre + t[ i ].l )continue ;//放
while( head <= tail && q[ head ] + t[ i ].l < j )++head ;
if( j < t[ i ].pre ){
int tmp = dp[ i-1 ][ j ] - j*t[ i ].val ;//移项后 dp[ i-1 ][ k ] - k*val[ i ]
while( head <= tail && tmp > dp[ i-1 ][ q[tail] ] - t[i].val*q[tail] )--tail ;//cz
q[ ++tail ] = j ; continue ;
}
else dp[i][j] = max( dp[i][j] , dp[ i-1 ][ q[head] ] + (j-q[head])*t[i].val ) ;
}
}
cout<<dp[M][N] ;
}