状态压缩DP

还有几道题正在整理。。还有几道题不会做。。
这几份题目都是类TSP问题。某一个参数小。可以用状态压缩DP可以解~~~

#include 
#include 
#include 
using namespace std;
const int N = 10, M = 1 << 10;
int w[N][N]; int dp[M][N];
string s[N];
int n, m, ans;


// updata the w[a][b] with the offset o;
int f(int a, int b, int o){
    int res = 0, o1, o2;
    if (o<0) o1 = -o, o2 = 0; else o1 = 0, o2 = o;

    for (int i=o1,j=o2;i> s[i];

    memset(w, 0, sizeof(w));
    for (int i=0;i> n;
    while (n!=0){
        init(); solve();
        cout << ans << endl;
        cin >> n;
    }
}
#include 
using namespace std;
const int N = 15, M = (1 << 15) - 1;
const int INF = 10000000;
int dp[M][N], w[N][N];
int n, m, k;
int ans;

void init(){
    int i, j;
    m = (1 << n); k--;
    int a[N], b[N];

    for (i=0;i> a[i] >> b[i];

    for (i=0;i> w[i][j];
            if (i==j) w[i][j] = -INF;
            else  w[i][j] = b[j] - a[j] - w[i][j];
        }

    for (i=0;i> n >> k){
        init();  solve(); // patch();
        cout << ans << endl;
    }
}

HOJ 2491. Sequences

Brief description :

将数列 {an} 划分成一些长度在 [l, r] 之间的子段,每个子段的得分等于首尾项的和。(注意是完美划分,不要留空隙。~)

Note :

单调队列练习题。。
dp[i] = max{dp[j] + a[j+1]} + a[i] | j 要满足条件
把 dp[i] 和 a[i+1] 存在一起简化维护。。

#include 
using namespace std;
const int INF = 0x7fffffff;
const int N = 500002;

int a[N], d[N], q[N], cz, op;
int n, l, r;

void push(int x){
    while (cz <= op && d[x] >= d[q[op]])
        op--;
    q[++op] = x;
}

void init(){
    scanf("%d%d", &l, &r);
    for (int i=1;i<=n;i++) scanf("%d", &a[i]);
    a[n+1] = 0;
}

void solve(){
    d[0] = a[1]; cz = 0, op = -1;

    for (int i=1;i> n){
        init(); solve();
        cout << d[n] << endl;
    }
}

External link :


http://acm.hit.edu.cn/judge/show.php?Proid=2941