阿青的博客 这是注释，耶！

Jun 13 学习笔记

13 Jun 2018

学习笔记

UVa 1629

题目

A rectangular cake with a grid of m * n unit squares on its top needs to be sliced into pieces. Several cherries are scattered on the top of the cake with at most one cherry on a unit square. The slicing should follow the rules below:

  1. each piece is rectangular or square;
  2. each cutting edge is straight and along a grid line;
  3. each piece has only one cherry on it.

Given the shape of the cake and the scatter of the cherries, you are supposed to find out the least total length of the cutting edges.

思路

记忆化搜索

考虑各边分别为u(up), d(down), l(left), r(right)的小矩形，设d[u][d][l][r]为小矩形还需要的切割长度。如果小矩形内没有樱桃，规定d[u][d][l][r] = INF (切出这样的矩形说明造成了浪费)，如果有一个，d[u][d][l][r] = 0，否则遍历所有可能的下一次切割方式，进行状态转移。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#define cur dp[u][d][l][r]

using namespace std;

const int INF = 0x3f3f3f3f;  

const int maxn = 25;

int n, m, k;
int cake[maxn][maxn];
int dp[maxn][maxn][maxn][maxn];

int sum(int u, int d, int l, int r) {
    int cnt = 0;
    for(int i = u; i < d; i++)
        for(int j = l; j < r; j++) {
            if(cake[i][j]) cnt++;
            if(cnt > 1) return 2; // consider cur needed for all cnt >= 2
        }
    return cnt;
}

int dfs(int u, int d, int l, int r) {
    if(cur != -1) return cur;
    int cnt = sum(u, d, l, r);
    if(cnt == 0) return cur = INF;
    if(cnt == 1) return cur = 0;

    cur = INF;
    // horizontal
    for(int i = u; i < d - 1; i++) {
        cur = min(cur, dfs(u, i + 1, l, r) + dfs(i + 1, d, l, r) + r - l);
    }
    // vertical
    for(int i = l; i < r - 1; i++) {
        cur = min(cur, dfs(u, d, l, i + 1) + dfs(u, d, i + 1, r) + d - u);
    }
    return cur;
}

int main() {
    int x, y;
    scanf("%d%d%d", &n, &m, &k);
    memset(cake, 0, sizeof(cake));
    memset(dp, -1, sizeof(dp));
    for(int i = 0; i < k; i++) {
        scanf("%d%d", &x, &y);
        cake[x - 1][y - 1]++;
    }

    dfs(0, n, 0, m);

    printf("%d", dp[0][n][0][m]);

    return 0;
}

UVa 1630

题目

折叠一个字符串，使得其成为一个尽量短的字符串 例如AAAAAA变成6(A)。 而且这个折叠是可以嵌套的，例如NEEEEERYESYESYESNEEEEERYESYESYES会变成2(N5(E)R3(YES))。数字和括号也计入字符数量的统计，求出最短折叠的字符串长度并输出该字符串。

思路

记忆化搜索

对于每一个从s到e的字符串进行如下检索：

  1. 是否能直接被折叠（是一个子串的几倍）
  2. 能否切割成两段子串，分别折叠后总长度更小

代码

#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <map>

using namespace std;

const int maxn = 100 + 5;  
const int INF = 1e8;  

string word;
string fold[maxn][maxn];
int d[maxn][maxn];
int n;

int check(int s, int e)  
{  
    for(int len = 1; len <= (e - s + 1) / 2; len++){
        if((e - s + 1) % len) continue;  
        bool flag = true;  
        for(int i = s; i + len <= e; i++){  
            if(word[i] != word[i + len]){  
                flag = false;  
                break;  
            }  
        }  
        if(flag) return len;  
    }  
    return 0;  
}  

int dp(int s, int e) {
    if(d[s][e] != -1) return d[s][e];

    if(s == e) {
        fold[s][e] = word[s];
        d[s][e] = 1;
        return 1;
    }

    int newlen = INF;
    int pos = -1;

    for(int i = s; i < e; i++) {
        int poss = dp(s, i) + dp(i + 1, e);
        if(poss < newlen) {
            newlen = poss;
            pos = i;
        }
    }
    fold[s][e] = fold[s][pos] + fold[pos + 1][e];

    int len = check(s, e);
    // printf("%d", len);

    if(len) {
        char prefix[5];
        sprintf(prefix, "%d", (e - s + 1) / len);
        string folded = prefix + string("(") + fold[s][s + len - 1] + string(")");
        // printf("%s", folded.c_str());
        if(folded.length() < newlen) {
            fold[s][e] = folded;
            newlen = folded.length();
        }
    }

    d[s][e] = newlen;
    return d[s][e];
}

int main() {
    memset(d, -1, sizeof(d));
    char strin[maxn];
    scanf ("%s", strin);
    word = strin;

    n = word.length();
    dp(0, n);

    printf("%d\n", d[0][n - 1]);
    string strout = fold[0][n - 1];
    printf("%s\n", strout.c_str());
}