动态规划专题(四)

本节内容主要写了一些普通dp的实践
大多数不涉及dp的优化
包括线性dp，树形dp，图上的dp等等

线性dp的单点增加思想

LA5841

const int maxn = 5000 + 10;
char p[maxn], q[maxn];
const int inf = 0x3f3f3f3f;

int f[2][maxn], cnt[2][maxn];
int N, M;
int sp[256 + 5], ep[256 + 5], sq[256 + 5], eq[256 + 5];
int k = 0;

void init() {
    Set(sp, inf);
    Set(sq, inf);
    Set(ep, 0);
    Set(eq, 0);
    N = strlen(p + 1);
    M = strlen(q + 1);

    _rep(i, 1, N) {
        sp[p[i]] = min(sp[p[i]], i);
        ep[p[i]] = i;
        //debug(ep[p[i]]);
    }
    _rep(i, 1, M) {
        sq[q[i]] = min(sq[q[i]], i);
        eq[q[i]] = i;
    }
}

void initdp() {
    Set(f, 0);
    Set(cnt, 0);

    k = 0;
}

void dp() {
    _rep(i, 0, N) {
        _rep(j, 0, M) {
            //
            if(i == 0 && j == 0) continue;

            int v1 = inf, v2 = inf;
            if(i) v1 = f[k ^ 1][j] + cnt[k ^ 1][j];
            if(j) v2 = f[k][j - 1] + cnt[k][j - 1];
            f[k][j] = min(v1, v2);

            if(i) {
                // Move p[i]
                cnt[k][j] = cnt[k ^ 1][j];
                if(i == sp[p[i]] && j < sq[p[i]]) cnt[k][j]++;
                if(i == ep[p[i]] && j >= eq[p[i]]) cnt[k][j]--;
            }
            else if(j) {
                // Move q[j]
                cnt[k][j] = cnt[k][j - 1];
                if(j == sq[q[j]] && i < sp[q[j]]) cnt[k][j]++;
                if(j == eq[q[j]] && i >= ep[q[j]]) cnt[k][j]--;
            }
        }
        k ^= 1;
    }
}

int main() {
    freopen("input.txt", "r", stdin);
    int T;
    scanf("%d", &T);

    while (T--) {
        scanf("%s", p + 1);
        scanf("%s", q + 1);
        init();
        //debug(p[1]);
        //debug(ep['A']);
        assert(ep[p[1]] != 0);

        initdp();
        dp();

        printf("%d\n", f[k ^ 1][M]);
    }
}

其他水题

UVA11584

const int maxn = 1000 + 10;
const int inf = 0x3f;
char str[maxn];
int vis[maxn][maxn];
int pali[maxn][maxn];
int N;

void init() {
    //
    Set(vis, 0);
    Set(pali, 0);
}

int f[maxn];
void initdp() {
    N = strlen(str + 1);
    Set(f, inf);
    f[0] = 0;
    _rep(i, 1, N) f[i] = i;
}

int isPali(int i, int j) {
    if(i >= j) return 1;
    if(str[i] != str[j]) return 0;

    if(vis[i][j]) return pali[i][j];
    vis[i][j] = true;

    return pali[i][j] = isPali(i + 1, j - 1);
}

void dp() {
    _rep(i, 1, N) _for(j, 0, i) {
        if(isPali(j + 1, i)) f[i] = min(f[i], f[j] + 1);
    }
}

int main() {
    freopen("input.txt", "r", stdin);
    int T;
    scanf("%d", &T);

    while (T--) {
        init();
        scanf("%s", str + 1);

        initdp();
        dp();

        printf("%d\n", f[N]);
    }
}

UVA11400

const int maxn = 1000 + 10;
const int inf = 0x3f;
int N;

int f[maxn];

class Light {
public:
    int V;
    int K;
    int C;
    int L;

    bool operator< (const Light& rhs) const {
        return V < rhs.V;
    }
};

Light l[maxn];
int sum[maxn];

void initdp() {
    sort(l + 1, l + 1 + N);

    Set(f, inf);
    Set(sum, 0);
    f[0] = 0;

    _rep(i, 1, N) sum[i] = sum[i - 1] + l[i].L;
}

void dp() {
    _rep(i, 1, N) {
        _rep(j, 0, i - 1) f[i] = min(f[i], f[j] + (sum[i] - sum[j]) * l[i].C + l[i].K);
    }
}

int main() {
    freopen("input.txt", "r", stdin);
    while (scanf("%d", &N) && N) {
        _rep(i, 1, N) scanf("%d%d%d%d", &l[i].V, &l[i].K, &l[i].C, &l[i].L);

        initdp();
        dp();
        cout << f[N] << endl;
    }
}

重点讲讲fgets的用法

注意事项1

fgets(char* str, int maxn, stdin);

最多读取的大小是maxn - 1的大小，因为字符串是以'\0'结尾的
当输入的数据大于maxn指定的大小的时候，fgets()会读取maxn - 1个字符
预留1个字符存储'\n'

注意事项2

'\n'也仅仅是一个普通字符，也会存入数组中
也就是说，如果你输入的字符长度n < maxn
fgets()存储
str的内存地址开始，往后第n + 2个字节
后面会多出来'\n'和'\0'

str[0, N + 1]存储'xxx \n\0'
str[N + 2, maxn]全部被'\0'填充

fgets()会存储换行符’\n’进入str[]中

也就是说，如果n < maxn
len = strlen(str) - 1才是字符串长度

或者人为处理
if(str[strlen(str) - 1] == '\n') str[strlen(str) - 1] = '\0';
n = strlen(str);

注意事项3

fgets()只是读取
读取到的字节会覆盖原地址的存储
没有覆盖到的保持原样

注意事项4

fgets()如果读取n > maxn的数据
只能在str[]中存储maxn - 1个字符

而多余的字符残留在缓存中
下一次输入必须要清空缓存

记忆化搜索和递推

水题(模版题)

UVA10003

const int maxn = 50 + 5;
int A[maxn];
int f[maxn][maxn], vis[maxn][maxn];
int N, L;

void init() {
    Set(f, 0);
    Set(vis, 0);
    A[0] = 0;
    A[N + 1] = L;
}

int dp(int i, int j) {
    if(i >= j - 1) return 0;
    if(vis[i][j]) return f[i][j];

    vis[i][j] = 1;
    int& ans = f[i][j];
    ans = -1;

    _rep(k, i + 1, j - 1) {
        int v = dp(i, k) + dp(k, j) + A[j] - A[i];
        if(ans < 0 || v < ans) ans = v;
    }
    return ans;
}

int main() {
    freopen("input.txt", "r", stdin);
    while (scanf("%d%d", &L, &N) == 2 && L) {
        init();

        _rep(i, 1, N) scanf("%d", &A[i]);
        printf("The minimum cutting is %d.\n", dp(0, N + 1));
    }
}

括号序列

LA2451

const int maxn = 100 + 5;
int f[maxn][maxn];
int N;
char str[maxn];

void init() {
    N = strlen(str);
}

void initdp() {
    Set(f, -1);
    _for(i, 0, N) {
        f[i + 1][i] = 0;
        f[i][i] = 1;
    }
}

bool match(char a, char b) {
    return (a == '(' && b == ')') || (a == '[' && b == ']');
}

void dp() {
    for(int i = N - 2; i >= 0; i--) {
        _for(j, i + 1, N) {
            f[i][j] = N;
            if(match(str[i], str[j])) f[i][j] = min(f[i][j], f[i + 1][j - 1]);

            _for(k, i, j) f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j]);
        }
    }
}

void print(int i, int j) {
    if(i > j) return;
    if(i == j) {
        if(str[i] == '(' || str[i] == ')') printf("()");
        else printf("[]");
        return;
    }

    if(match(str[i], str[j]) && f[i][j] == f[i + 1][j - 1]) {
        printf("%c", str[i]);
        print(i + 1, j - 1);
        printf("%c", str[j]);
        return;
    }

    _for(k, i, j) {
        if(f[i][j] == f[i][k] + f[k + 1][j]) {
            print(i, k);
            print(k + 1, j);
            return;
        }
    }
}

void read(char* str) {
    fgets(str, maxn, stdin);
}

int main() {
    freopen("input.txt", "r", stdin);
    int T;
    scanf("%d", &T);
    getchar();

    while (T--) {
        read(str);
        read(str);
        if(str[strlen(str) - 1] == '\n') str[strlen(str) - 1] = '\0';
        init();
        //debug(N);

        initdp();
        dp();
        print(0, N - 1);
        cout << endl;

        if(T) cout << endl;
    }
}

和计算几何有关的dp

以上算法的状态转移方程归纳如下

LA3132

// computation Geometry header
const double eps = 1e-10;
const double PI = acos(-1);
const double PI2 = 2 * PI;

int dcmp(double x) {
    if(fabs(x) < eps) return 0;
    else return x < 0 ? -1 : 1;
}

class Point {
public:
    double x, y;
    Point(double x = 0, double y = 0) : x(x), y(y) {}
};

typedef Point Vector;

bool operator< (const Point& lhs, const Point& rhs) { return lhs.x < rhs.x || (lhs.x == rhs.x && lhs.y < rhs.y); }
bool operator== (const Point& lhs, const Point& rhs) { return dcmp(lhs.x - rhs.x) == 0 && dcmp(lhs.y - rhs.y) == 0; }

Vector operator+ (const Vector& lhs, const Vector& rhs) { return Vector(lhs.x + rhs.x, lhs.y + rhs.y); }
Vector operator- (const Vector& lhs, const Vector& rhs) { return Vector(lhs.x - rhs.x, lhs.y - rhs.y); }
Vector operator* (const Vector& lhs, double p) { return Vector(lhs.x * p, lhs.y * p); }
Vector operator/ (const Vector& lhs, double p) { return Vector(lhs.x / p, lhs.y / p); }
double Dot(const Vector& A, const Vector& B) { return A.x * B.x + A.y * B.y; }
double Length(const Vector& A) { return sqrt(Dot(A, A)); }
double Angle(const Vector& A, const Vector& B) { return acos(Dot(A, B) / Length(A) / Length(B)); }
double Cross(const Vector& A, const Vector& B) { return A.x * B.y - A.y * B.x; }

Point readPoint() {
    double x, y;
    scanf("%lf%lf", &x, &y);
    return Point(x, y);
}

Point getLineIntersection(const Point& P, const Vector& v, const Point& Q, const Vector& w) {
    Vector u = P - Q;
    double t = Cross(w, u) / Cross(v, w);
    return P + v * t;
}

Vector Rotate(const Vector& A, double rad) {
    return Vector(A.x * cos(rad) - A.y * sin(rad), A.x * sin(rad) + A.y * cos(rad));
}

bool segmentProperIntersection(const Point& a1, const Point& a2, const Point& b1, const Point& b2) {
    double c1 = Cross(a2 - a1, b1 - a1), c2 = Cross(a2 - a1, b2 - a1);
    double c3 = Cross(b2 - b1, a1 - b1), c4 = Cross(b2 - b1, a2 - b1);
    return dcmp(c1) * dcmp(c2) < 0 && dcmp(c3) * dcmp(c4) < 0;
}

bool onSegment(Point p, Point a1, Point a2) {
    return dcmp(Cross(a1 - p, a2 - p)) == 0 && dcmp(Dot(a1 - p, a2 - p)) < 0;
}

double distanceToLine(const Point& P, const Point& A, const Point& B) {
    Vector v1 = B - A, v2 = P - A;
    return fabs(Cross(v1, v2)) / Length(v1);
}

double distanceToSegment(const Point& P, const Point& A, const Point& B) {
    if(A == B) return Length(P - A);
    Vector v1 = B - A, v2 = P - A, v3 = P - B;

    if(dcmp(Dot(v1, v2)) < 0) return Length(v2);
    else if(dcmp(Dot(v1, v3) > 0)) return Length(v3);
    else return fabs(Cross(v1, v2)) / Length(v1);
}

Vector Normal(Vector A) {
    double L = Length(A);
    return Vector(-A.y / L, A.x / L);
}


class Circle {
public:
    Point c;
    double r;
    Circle(Point c = {0.0, 0.0}, double r = 0.0) : c(c), r(r) {}
    Point point(double rad) {
        return Point(c.x + r * cos(rad), c.y + r * sin(rad));
    }
};

typedef Circle Pan;

class Line {
public:
    Point p;
    Vector v;

    Line(Point p, Vector v) : p(p), v(v) {}

    Point point(double t) {
        return p + v *  t;
    }
    Line move(double d) {
        return Line(p + Normal(v) * d, v);
    }
};

double angle(Vector v) {
    return atan2(v.y, v.x);
}

int getLineCircleIntersection(Line L, Circle C, double& t1, double& t2, vector<Point>& sol) {
    double a = L.v.x, b = L.p.x - C.c.x, c = L.v.y, d = L.p.y - C.c.y;
    double e = a * a + c * c, f = 2 * (a * b + c * d), g = (b * b + d * d - C.r * C.r);
    double delta = f * f - 4 * e * g;

    if(dcmp(delta) < 0) return 0;
    if(dcmp(delta) == 0) {
        t1 = t2 = -f / (2 * e);
        sol.push_back(L.point(t1));
        return 1;
    }

    t1 = (-f - sqrt(delta)) / (2 * e);
    sol.push_back(L.point(t1));
    t2 = (-f + sqrt(delta)) / (2 * e);
    sol.push_back(L.point(t2));

    return 2;
}

double Normalize(double rad, double base = PI) {
    return rad - PI2 * floor((rad + PI - base) / PI2);
}

void getCircleCircleIntersection(Circle C1, Circle C2, vector<double>& rad) {
    double d = Length(C1.c - C2.c);
    if(dcmp(d) == 0) {
        return;
    }

    if(dcmp(C1.r + C2.r - d) < 0) return;
    if(dcmp(fabs(C1.r - C2.r) - d) > 0) return;

    double a = angle(C2.c - C1.c);
    double da = acos((C1.r * C1.r + d * d - C2.r * C2.r) / (2 * C1.r * d));

    rad.push_back(Normalize(a - da));
    rad.push_back(Normalize(a + da));
}

typedef vector<Point> Polygon;

int isPointInPolygon(const Point& p, const Polygon& poly) {
    int n = poly.size();
    int wn = 0;

    _for(i, 0, n) {
        const Point& p1 = poly[i];
        const Point& p2 = poly[(i+1) % n];

        if(p1 == p || p2 == p || onSegment(p, p1, p2)) return -1;
        int k = dcmp(Cross(p2 - p1, p - p1));
        int d1 = dcmp(p1.y - p.y);;
        int d2 = dcmp(p2.y - p.y);
        if(k > 0 && d1 <= 0 && d2 > 0) wn++;
        if(k < 0 && d2 <= 0 && d1 > 0) wn--;
    }

    if(wn != 0) return 1;
    return 0;
}

// poly[a], poly[b]
// (poly[a], poly[b]) is diagonal
bool isDiagonal(const Polygon& poly, int a, int b) {
    int n = poly.size();
    _for(i, 0, n) {
        if(i != a && i != b && onSegment(poly[i], poly[a], poly[b])) return false;
    }

    _for(i, 0, n) {
        if(segmentProperIntersection(poly[i], poly[(i+1) % n], poly[a], poly[b])) return false;
    }

    Point midp = (poly[a] + poly[b]) * 0.5;
    return isPointInPolygon(midp, poly) == 1;
}


// then solve the problem
const int maxn = 100 + 5;
const int inf = 1e9;
double f[maxn][maxn];


void initdp(const Polygon& poly) {
    int n = poly.size();
    _for(i, 0, n) _for(j, 0, n) f[i][j] = -1;
}

double dp(const Polygon& poly) {
    int n = poly.size();
    _forDown(i, n - 2, 0) _for(j, i + 1, n) {
        if(i + 1 == j) f[i][j] = 0;
        else if(!(i == 0 && j == n - 1) && !isDiagonal(poly, i, j)) f[i][j] = inf;
        else {
            f[i][j] = inf;
            _for(k, i + 1, j) {
                double m = max(f[i][k], f[k][j]);
                double area = fabs(Cross(poly[j] - poly[i], poly[k] - poly[i])) * 0.5;
                m = max(m, area);
                f[i][j] = min(f[i][j], m);
            }
        }
    }
    return f[0][n - 1];
}

int main() {
    freopen("input.txt", "r", stdin);
    int T, N;
    scanf("%d", &T);

    while (T--) {
        scanf("%d", &N);
        double x, y;
        Polygon poly;

        _for(i, 0, N) {
            scanf("%lf%lf", &x, &y);
            poly.push_back(Point(x, y));
        }

        assert(poly.size() > 0);
        initdp(poly);
        printf("%.1lf\n", dp(poly));
    }
}