首页 > 代码库 > HDU 1565 方格取数(1) (状态压缩DP)
HDU 1565 方格取数(1) (状态压缩DP)
HDU 1565 方格取数(1) (状态压缩DP)
ACM
题目地址:
HDU 1565 方格取数(1)
题意:
中文。
分析:
dp[i][j]表示前i行状态j的最优解。
先预处理出符合条件的数,17000+个(n在20以内)。
不过感觉复杂度挺高的会T,但是却能A。
这题的正解应该是最小割,回头补下。
代码:
/* * Author: illuz <iilluzen[at]gmail.com> * File: 1565_dp.cpp * Create Date: 2014-09-19 23:30:19 * Descripton: dp */ #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; #define repf(i,a,b) for(int i=(a);i<=(b);i++) typedef long long ll; const int N = 1<<21; int n, st[N], stn; int dp[2][N]; int ans, g[25][25]; void pre() { repf (i, 0, (1<<20)) { if (i & (i<<1)) continue; else st[stn++] = i; } } void solve() { if (n == 0) { cout << 0 << endl; return; } int tot = 1<<n; ans = 0; // first line for (int i = 0; st[i] < tot; i++) { dp[0][i] = 0; repf (j, 0, n - 1) if (st[i]&(1<<j)) dp[0][i] += g[0][j]; ans = max(ans, dp[0][i]); } // 2~n line repf (i, 1, n - 1) { for (int j = 0; st[j] < tot; j++) { int tmp = 0; dp[i&1][j] = 0; // can get tmp value repf (k, 0, n - 1) { if (st[j]&(1<<k)) tmp += g[i][k]; } for (int k = 0; st[k] < tot; k++) { if (!(st[j]&st[k])) dp[i&1][j] = max(dp[i&1][j], tmp + dp[!(i&1)][k]); } ans = max(ans, dp[i&1][j]); } } cout << ans << endl; return; } int main() { ios_base::sync_with_stdio(0); pre(); while (cin >> n) { repf (i, 0, n - 1) repf (j, 0, n - 1) cin >> g[i][j]; solve(); } return 0; }
HDU 1565 方格取数(1) (状态压缩DP)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。