Topic 22 interval DP

ZOJ 3537 Cake

Judge closure + optimal triangulation

Note that the calculated closure is used to calculate the transfer

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
int m,f[400][400],dp[400][400];
struct Point{
    int x,y;
    Point(){}
    Point(int xx,int yy):x(xx),y(yy){}
    void read(){
        scanf("%d%d",&x,&y);
    }
    bool operator < (const Point &other)const{
        if(x == other.x)
            return y < other.y;
        return x < other.x;
    }
    Point operator - (const Point &other)const{
        return Point(x - other.x,y - other.y);
    }
};
Point p[400],ch[400];
int n;
double Cross(Point A,Point B){
    return A.x * B.y - A.y * B.x;
}
int ConvexHull(){
    sort(p,p+n);
    int cnt = 0;
    for(int i = 0; i < n; i++){
        while(cnt > 1 && Cross(ch[cnt-1] - ch[cnt-2],p[i] - ch[cnt-2]) <= 0) cnt--;
        ch[cnt++] = p[i];
    }
    int k = cnt;
    for(int i = n-2; i >= 0; i--){
        while(cnt > k && Cross(ch[cnt-1] - ch[cnt-2],p[i] - ch[cnt-2]) <= 0) cnt--;
        ch[cnt++] = p[i];
    }
    if(n > 1) cnt--;
    return cnt;
}
int calc(Point a,Point b){
    return (abs(a.x + b.x) * abs(a.y + b.y)) % m;
}
int main(){
    while(scanf("%d%d",&n,&m) != EOF){
        memset(p,0,sizeof(p));
        memset(ch,0,sizeof(ch));
        memset(f,0,sizeof(f));
        for(int i = 0; i < n; i++){
            p[i].read();
        }
        if(n == 3){
            puts("0");
            continue;
        }
        if(ConvexHull() < n){
            printf("I can't cut.\n");
        }
        else{
            for(int i = 0; i < n; i++){
                for(int j = i+2; j < n; j++){
                    f[i][j] = f[j][i] = calc(ch[i],ch[j]);
                }
            }
            for(int i = 0; i < n; i++){
                for(int j = 0; j < n; j++){
                    dp[i][j] = INF;
                }
                dp[i][(i+1)%n] = 0;
            }
             for (int len = 3; len <= n; len++) {
                for (int i = 0; i + len - 1 < n; i++) {
                    int j = i + len - 1;
                    for (int k = i + 1; k <= j - 1; k++) {
                        dp[i][j] = min(dp[i][j],dp[i][k]+dp[k][j]+f[i][k]+f[k][j]);
                    }
                }
            }
            printf("%d\n",dp[0][n-1]);
        }
    }
    return 0;
}

LightOJ 1422 Halloween Costumes

General idea:

N banquets. For each banquet, a dress should be worn. The dress can be worn, but the stripped one can't be used again. You must attend the banquet in order. From the first to the nth, ask how many dresses you need to attend these banquets at least

Idea:

When c[j-1] = c[j], obviously DP [i] [J] = DP [i] [J-1]

Update is an update. When the dress of the k-th ball is consistent with the dress of the j-th ball, it is assumed that the dress of the k-th ball is always worn

#include <bits/stdc++.h>

using namespace std;

const int N = 1e2 + 5;
typedef long long LL;
int t, a[N], dp[N][N], cases = 0;
int main() {
    cin >> t;
    while (t--) {
        cases++;
        memset(dp, 0x3f, sizeof dp);
        int n;
        cin >> n;
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        for (int i = 0; i < n; i++) {
            dp[i][i] = 1;
        }
        for (int len = 2; len <= n; len++) {
            for (int i = 0; i + len - 1 < n; i++) {
                int j = i + len - 1;
                if (a[j] == a[j - 1])
                    dp[i][j] = dp[i][j - 1];
                else
                    dp[i][j] = dp[i][j - 1] + 1;
                for (int k = i; k < j; k++) {
                    if (a[k] == a[j]) {
                        dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j - 1]);
                    }
                }
            }
        }
        printf("Case %d: %d\n", cases, dp[0][n - 1]);
    }
    return 0;
}

POJ 2955 Brackets

General idea:

Give a string and ask what is the longest interval that satisfies the matching of parentheses

The matching parentheses are:

(), [], (()), ()[], ()[()]

Idea:

When s [ i ] = = s [ j ] s[i]==s[j] When s[i]==s[j], d p [ i ] [ j ] = = d p [ i + 1 ] [ j − 1 ] + 2 dp[i][j]==dp[i+1][j-1]+2 dp[i][j]==dp[i+1][j−1]+2

Then transfer directly

#include <math.h>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
using namespace std;
const int N = 1e2 + 5;
typedef long long LL;
int dp[N][N];
int main() {
    string s;
    while (cin >> s) {
        if (s == "end") break;
        int n = s.size();
        memset(dp, 0, sizeof dp);
        int res = 0;
        for (int len = 2; len <= n; len++) {
            for (int i = 0; i + len - 1 < n; i++) {
                int j = i + len - 1;
                if ((s[i] == '(' && s[j] == ')') ||
                    (s[i] == '[' && s[j] == ']'))
                    dp[i][j] = dp[i + 1][j - 1] + 2;
                for (int k = i; k < j; k++) {
                    dp[i][j] = max(dp[i][k] + dp[k + 1][j], dp[i][j]);
                }
                res = max(res, dp[i][j]);
            }
        }
        cout << res << endl;
    }
    return 0;
}

CodeForces 149D Coloring Brackets

General idea:

Give a string of parentheses that can be matched. Now color these parentheses to meet the following requirements:

For each pair of paired parentheses, there is and only one parenthesis colored

If adjacent brackets are dyed, the color cannot be the same

Each bracket is either not colored, red or green

Idea:

First, use the stack to match the parentheses

Write the interval dp with dfs, enumerate the colors on both sides, and then transfer

If the left and right endpoints of the current interval are paired, you can directly enter the next interval

Otherwise, enumerate the paired right parentheses corresponding to the left endpoint, and enumerate all the colors

#include <bits/stdc++.h>

using namespace std;

const int N = 7e2 + 5;
typedef long long LL;
LL dp[N][N][5][5];
string s;
const LL mod = 1e9 + 7;
int n, ne[N];
stack<int> st;

LL dfs(int l, int r, int c1, int c2) {
    LL res = 0;
    if (l >= r) return dp[l][r][c1][c2] = 0LL;
    if (dp[l][r][c1][c2] != -1) return dp[l][r][c1][c2];
    if (ne[l] == r) {  //If the left and right endpoints of this interval match exactly, the scheme of the left and right endpoints has been fixed
        if ((c1 == 0 && c2 != 0) || (c2 == 0 && c1 != 0)) {  //Current match must be legal
            if (l + 1 == r) return dp[l][r][c1][c2] = 1LL;
            for (int i = 0; i < 3; i++) {
                for (int j = 0; j < 3; j++) {
                    if (((i == 0) || (c1 == 0) || (i != c1)) &&
                        ((j == 0) || (c2 == 0) || (j != c2))) {
                        res = (res + dfs(l + 1, r - 1, i, j)) % mod;
                    }
                }
            }
        }
    } else {
        int k = ne[l];
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if ((i == 0) || (j == 0) || (i != j)) {
                    res = (res + dfs(l, k, c1, i) * dfs(k + 1, r, j, c2) % mod) %mod;
                }
            }
        }
    }

    return dp[l][r][c1][c2] = res;
}

int main() {
    cin >> s;
    memset(dp, -1, sizeof dp);
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == '(')
            st.push(i);
        else {
            ne[st.top()] = i;
            st.pop();
        }
    }
    n = s.size();
    LL res = 0;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            res = (res + dfs(0, n - 1, i, j)) % mod;
        }
    }
    cout << res << endl;
    return 0;
}

POJ 1651 Multiplication Puzzle

General idea:

Given n numbers, take out one number from the number not taken out each time. The cost is the product of this number and the number not taken out on both sides. The leftmost and rightmost numbers cannot be taken. Ask what is the minimum cost

Idea:

Just enumerate the midpoint transfer. Note that the transfer interval is i, k and k, J, not i, k and k + 1, J

Interval dp is to carefully analyze the interval boundary

#include <math.h>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
using namespace std;

const int N = 1e2 + 5;
typedef long long LL;
int n;
LL a[N], dp[N][N];
int main() {
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    memset(dp, 0x3f, sizeof dp);
    for (int i = 0; i < n - 1; i++) dp[i][i + 1] = 0;
    for (int len = 3; len <= n; len++) {
        for (int i = 0; i + len - 1 < n; i++) {
            int j = i + len - 1;
            for (int k = i + 1; k < j; k++) {
                dp[i][j] =
                    min(dp[i][j], dp[i][k] + dp[k][j] + a[i] * a[k] * a[j]);
            }
        }
        }
    cout << dp[0][n - 1] << endl;
    return 0;
}

ZOJ 3469 Food Delivery

General idea:

There is a restaurant on the x-axis and n points for takeout. The coordinate of the restaurant is x and the speed of the workers is v − 1 v^{-1} v − 1, i.e. 1/v meter per minute. Give the x coordinate and b of n points. If the takeout is not delivered, the customer will be unhappy, and the unhappiness index increases by b every minute. Ask what kind of delivery strategy to minimize the total unhappiness index and of all customers.

Idea:

It can be deduced that when the takeout at both ends of the interval l to r needs to be delivered, it must be transferred from the interval l to r-1 or l+1 to r, that is, the points inside the interval have been delivered, otherwise it will deliver the points inside the interval first

However, employees must be either at the left end point of the interval or at the right end point of the interval, so they need to open more one-dimensional maintenance. Is it on the left or right

#include <bits/stdc++.h>

using namespace std;

const int N = 1e3 + 5;
typedef long long LL;
int n, v, x;
struct node {
    int pos, b;
} a[N];
int dp[N][N][2], sum[N];
bool cmp(node a, node b) { return a.pos < b.pos; }
int main() {
    while (scanf("%d%d%d", &n, &v, &x) != EOF) {
        for (int i = 1; i <= n; i++) scanf("%d%d", &a[i].pos, &a[i].b);
        n++;
        a[n].pos = x, a[n].b = 0;
        sort(a+1, a + n + 1,cmp);
        int pos = 0;
        for (int i = 1; i <= n; i++) {
            if (a[i].pos == x) {
                pos = i;
                break;
            }
        }
        for (int i = 1; i <= n; i++) {
            sum[i] = sum[i - 1] + a[i].b;
        }
        memset(dp, 0x3f, sizeof dp);
        for (int i = pos; i >=1 ; i--) {
            for (int j = pos; j <= n; j++) {
                if (i == j) {
                    dp[i][j][0] = dp[i][j][1] = 0;
                    continue;
                }
                int mid = sum[i - 1] - sum[0] + sum[n] - sum[j];
                dp[i][j][0] = min(dp[i][j][0],dp[i + 1][j][0] + (mid+a[i].b) * (a[i + 1].pos - a[i].pos));
                dp[i][j][0] = min(dp[i][j][0],dp[i + 1][j][1] + (mid+a[i].b) * (a[j].pos - a[i].pos));
                dp[i][j][1] = min(dp[i][j][1],dp[i][j-1][0] + (mid+a[j].b) * (a[j].pos - a[i].pos));
                dp[i][j][1] = min(dp[i][j][1],dp[i][j-1][1] + (mid+a[j].b) * (a[j].pos - a[j-1].pos));
            }
            
        }
        cout << min(dp[1][n][0], dp[1][n][1]) * v << endl;
    }
    return 0;
}

HDU 4283 You Are the One

General idea:

There are n people. v[i] represents everyone's anger value. Now they perform on the stage in turn. If I is the k-th person on the stage, his anger value is (k-1) * v[i] now there is a stack that allows some people to enter the stack and the people behind to perform on the stage first. In this way, part of the order can be changed to find the minimum sum of everyone's anger value

Idea:

We consider interval [l, r]. If the first person is the k-th player in the interval, the person in interval [l+1, r] should play before the first one, and the person in interval [l+k + 1, r] must play after the first person. Such an interval is divided into two intervals.

DP [i + 1] [i+k - 1] represents the depression value of the first k - 1 person, a[i] * (k-1) represents the depression value of the ith person, and the total depression value of these people from i+k to j increases by k * (sum[j] - sum[i+k-1])

#include <bits/stdc++.h>

using namespace std;

const int N = 1e2 + 5;
typedef long long LL;
int n, dp[N][N], t, a[N], sum[N], cases;
int main() {
    cin >> t;
    while (t--) {
        cases++;
        cin >> n;
        for (int i = 1; i <= n; i++) cin >> a[i], sum[i] = sum[i - 1] + a[i];
        memset(dp, 0, sizeof dp);
        for (int len = 1; len <= n; len++) {
            for (int i = 1; i + len - 1 <= n; i++) {
                int j = i + len - 1;
                dp[i][j] = 0x3f3f3f3f;
                if (len==1) {
                    dp[i][j] = 0;
                    continue;
                }
                for (int k = 1; k <= len; k++) {
                    dp[i][j] =
                        min(dp[i][j], dp[i + 1][i + k - 1] + a[i] * (k - 1) +dp[i+k][j]+
                                          k * (sum[j] - sum[i + k-1]));
                }
            }
        }
        printf("Case #%d: %d\n", cases, dp[1][n]);
    }
    return 0;
}

HDU 2476 String painter

General idea:

Give two strings s1,s2. For each operation, any sub segment in the s1 string can be changed into another character. Ask at least how many steps are required to change s1 string into s2 string.

Idea:

This question first considers how to convert an empty string into s2,
F [i] [J] represents the minimum number of times from empty string to s2,
Then f [i] [J] = s [i + 1] [J] + 1,
If [i + 1, j] has a k such that S2 [i] = = S2 [k], then f [i] [J] = min {f [i + 1] [k] + F [K + 1] [J]},
That is, i and k use the same transformation

Then consider the cost of brushing s1 to s2
Let sum[i] represent the number of times s1[1,i] is brushed to s2[1,i]
When s1[i]==s2[i], you can not brush. Obviously, sum[i]=sum[i-1]
Otherwise, find the minimum number of times sum[i]=min(sum[j] + f [j+1] [i]) in the interval

#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;

int n, m;

int f[N][N], sum[N];

char s[N], t[N];

int main() {
    while (cin >> s) {
        cin >> t;
        memset(f, 0, sizeof f);
        memset(sum, 0, sizeof sum);
        int len = strlen(s);
        for (int i = 0; i < len; ++i) f[i][i] = 1;
        for (int i = 0; i < len; ++i)
            for (int j = i - 1; j >= 0; --j) {
                f[j][i] = f[j + 1][i] + 1;
                for (int k = j + 1; k <= i; ++k)
                    if (t[j] == t[k])
                        f[j][i] = min(f[j][i], f[j + 1][k] + f[k + 1][i]);
            }
        for (int i = 0; i < len; ++i) sum[i] = f[0][i];
        if (s[0] == t[0]) sum[0] = 0;
        for (int i = 1; i < len; ++i) {
            if (s[i] == t[i])
                sum[i] = min(sum[i], sum[i - 1]);
            else
                for (int j = 0; j < i; ++j)
                    sum[i] = min(sum[i], sum[j] + f[j + 1][i]);
        }
        cout << sum[len - 1] << endl;
    }
}