本文主要是介绍状态dp总结，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
zoj 3631 N 个数中选若干数和（只能选一次）<=M 的最大值
const int Max_N = 38 ;
int a[1<<16] , b[1<<16] , x[Max_N] , e[Max_N] ;void GetNum(int g[] , int n , int s[] , int &m){ int i , j , t ;m = 0 ;for(i = 0 ; i < (1<<n) ; i++){t = 0 ;for(j = 0 ; j < n ; j++){if(i & (1<<j)) t+= g[j] ;}s[m++] = t ;}
}int Ans(int asize , int bsize , int m){ //两个有序表中寻找和<=m的最大数int i , j , t , ans = 0 ;j = bsize-1 ;for(i = 0 ; i < asize ; i++){for( ; j >= 0 ; j--){t = a[i] + b[j] ;if(t <= m){ans = max(ans , t) ;if(t == m) return t ;break ;}}}return ans ;
}int main(){int i , n , m , j , k , asize , bsize ;while(scanf("%d%d" ,&n ,&m) != EOF){for(i = 1 ; i <= n ; i++)scanf("%d" ,&x[i]) ;k = n>>1 ;for(j = 0 , i = 1 ; i <= k ; i++) e[j++] = x[i] ;GetNum(e , j , a , asize) ;for(j = 0 , i = k+1 ; i <= n ; i++) e[j++] = x[i] ;GetNum(e , j , b , bsize) ;sort(a , a+asize) ;sort(b , b+bsize) ;printf("%d\n" ,Ans(asize , bsize , m)) ;}return 0 ;
}zoj2297 和n个人打架，跟每个人打架需要消耗一定的HP，打赢之后也能恢复一定的HP，初值HP为100 ， 中间最HP为100，打架顺序随便，判断最后剩下的HP最大值。
const int Max_N = 20 ;
int dp[1<<Max_N] , down[Max_N] , up[Max_N] ;
int n ;int DP(){int i , j , s ;for(i = 0 ; i < (1<<n) ; i++) dp[i] = -1 ;dp[0] = 100 ;for(i = 0 ; i < (1<<n) ; i++){if(dp[i] == -1) continue ;for(j = 0 ; j < n ; j++){if(i & (1<<j)) continue ;if(dp[i] < down[j]) continue ; //注意这个地方s = dp[i] - down[j] + up[j] ;if(s >= 100) s = 100 ;dp[i ^ (1<<j)] = max(dp[i ^ (1<<j)] , s) ;}}return dp[(1<<n) - 1] ;
}
zoj 3777 。N个人站位，N!种方式，value[i][j](i个人站在j的价值)。求排列好后总的value值>=m的总情况。
dp[i][j] : i这个状态，价值>=j的情况数。
int DP(){int i , j , k , row ;for(i = 0 ; i < (1<<N) ; i++)for(j = 0 ; j <= M ; j++) dp[i][j] = 0 ;dp[0][0] = 1 ;for(i = 0 ; i < (1<<N) ; i++){for(row = 0 , j = 0 ; j < N ; j++)if(i & (1<<j)) row++ ;for(j = 0 ; j < N ; j++){if(i & (1<<j)) continue ;for(k = 0 ; k <= M ; k++){int n = k + g[row+1][j] ;if(n >= M)dp[i^(1<<j)][M] += dp[i][k] ;elsedp[i^(1<<j)][n] += dp[i][k] ;}}}return dp[(1<<N) - 1][M] ;
}zoj 3471 不超过10种气体，两两之间相互碰撞可以产生一定的能量，如a碰b，那么b气体就消失，自身不能碰自身，问最后所能得到的最大能量。
分析：这个题不是旅行商问题，每个气球可以多次碰撞其他的气球。1表示气体死了， 0 表示气球还在，dp[i]表示i状态时的最大能量。每次利用dp[i]这个状态的时候， 用到的求j,k都是活的，可以让k撞j, k活着，j死去。那么更新的值就是dp[i ^ (1<<j)] 。初始都是活的状态为dp[0]。
int DP(){int i , j , k , row , limit = (1<<n) ;for(i = 0 ; i < limit ; i++)dp[i] = -1 ;dp[0] = 0 ;for(i = 0 ; i < limit ; i++){if(dp[i] == -1) continue ;for(j = 0 ; j < n ; j++){if(i & (1<<j)) continue ;for(k = 0 ; k < n ; k++){if(j == k) continue ;if(i & (1<<k)) continue ;dp[i ^ (1<<j)] = max(dp[i ^ (1<<j)] , dp[i] + g[k][j]) ;}}}return *max_element(dp , dp+limit) ;
}int main(){int i , j ;while(cin>>n && n){for(i = 0 ; i < n ; i++)for(j = 0 ; j < n ; j++) scanf("%d" ,&g[i][j]) ;printf("%d\n" ,DP()) ;}return 0 ;
}HDU 1565 n*n的矩阵取数，满足任意2个数不相邻，和最大
vector<int> state ;
int g[21][21] ;
int dp[21][17800] ;
int n ;
int sum(int row , int s){int t = 0 ;for(int i = 0 ; i < n ; i++){if(s & (1<<i)) t += g[row][i] ;}return t ;
}int DP(){int i , j , row , ans = 0 ;memset(dp , 0 , sizeof(dp)) ;for(i = 0 ; state[i] < (1<<n) ; i++) dp[1][i] = sum(1 , state[i]) ;for(row = 2 ; row <= n ; row++){for(i = 0 ; state[i] < (1<<n) ; i++){for(j = 0 ; state[j] < (1<<n) ; j++){if(state[i] & state[j]) continue ;dp[row][i] = max(dp[row][i] , dp[row-1][j] + sum(row , state[i])) ;}}}for(i = 0 ; state[i] < (1<<n) ; i++)ans = max(ans , dp[n][i]) ;return ans ;
}int main(){int i , j ;state.clear() ;for(i = 1 ; i < (1<<20) ; i++){if(i & (i<<1)) continue ;state.push_back(i) ;}while(scanf("%d" ,&n) != EOF){for(i = 1 ; i <= n ; i++)for(j = 0 ; j < n ; j++)scanf("%d" ,&g[i][j]) ;printf("%d\n" ,DP()) ;}return 0 ;
}
这篇关于状态dp总结的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
