hdu5045(dp + 狀態壓縮)

hdu5045(dp + 狀態壓縮)

題意：

給出ｎ個人，ｍ道題；每道題只能一個人做；現在給出ｎ行ｍ列．是每個人做每一道題的成功率；

你現在要選出哪些人做哪些題，使成功率和最大．但是有一個條件做到任意一題時，做最多的人只能比做最少的人多做一道；

就是如果１０個人，那麼前１０題必須一人一題；

思路：

因為限制條件，所以前ｎ道題，必須分給ｎ個人一人一道，那麼每人只能做一次；

那麼用狀態壓縮表示哪些人做過了；

比如５個人００１１０；那麼下一道題就可以選擇剩下的３個人做，並且比較出一個最優的選擇；

當狀態變成１１１１１時，就要重新置零；

所以用一個ｄｐ［ｉ］［ｊ］表示前ｉ道題，已經做的人的狀態是ｊ；

ＡＣ：

#include
#include
#include
using namespace std;

double p[15][1005];
double dp[1005][1 << 10];
int n,m;
double solve() {
	for(int i = 0; i <= m; i++) {
		for(int j = 0 ; j < (1 << n); j++) {
			dp[i][j] = -1.0;
		}
	}
	dp[0][0] = 0;
	for(int i = 0; i < m; i++) {
		for(int k = 0; k < (1 << n); k++) {
			if(dp[i][k] < 0)
				continue;
			int s;
			for(int j = 0; j < n; j++) {
				int tmp = 1 << j;
				if(k & tmp) continue;
				s = k | tmp;
				if(s == (1 << n) - 1)
					s = 0;
				dp[i + 1][s] = max(dp[i + 1][s], dp[i][k] + p[j][i]);
			}
		}
	}
	double ans = 0.0;
	for(int i = 0; i < (1 << n); i++) {
		ans = max(ans, dp[m][i]);
	}
	return ans;
}
int main() {
	int t;
	int cas = 1;
	scanf("%d",&t);
	while(t--) {
		scanf("%d%d",&n,&m);
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < m; j++) {
				scanf("%lf",&p[i][j]);
			}
		}
		printf("Case #%d: %.5lf\n",cas++, solve());
	}
}