第一题

回文数变换 时间限制： 1000MS 内存限制： 65536KB 题目描述： 所谓回文数就是一个数字，从左边读和从右边读的结果都是一样的，例如12321。
现在有一个只包含1、2、3、4的数字，你可以通过在任意位置增加一位数字或者删除一位数字来将其变换成一个回文数。但是增加或删除不同数字所需要的代价是不一样的。
已知增加和删除每个数字的代价如下：
增加一个1，代价：100；删除一个1，代价：120。
增加一个2，代价：200；删除一个2，代价：350。
增加一个3，代价：360；删除一个3，代价：200。
增加一个4，代价：220；删除一个4，代价：320。
请问如何通过最少的代价将一个数字变换为一个回文数。当然，如果一个数字本身已经是一个回文数（包括一位数，例如：2），那么变换的代价为0。


输入描述 单组输入。
输入一个由1、2、3、4组成的正整数，正整数位数<=100位。【提示：采用字符串输入】
输出描述 输出一个整数，表示将输入数字变换为一个回文数所需的最少代价。

样例输入 12322 样例输出 300
提示 增加一个1并增加一个2，将输入正整数变为1223221或者2123212，所需代价最小，为：100+200=300。

思路：

　　显然，这是一道DP题，以为之前也遇到了几个相似的题目所以做起来并没有感觉太难，思路也很清晰，但是不知道为什么最后提交的时候只通过了9%。

代码：

#include <iostream>
#include <map>
#include <string>
#include <vector>

using namespace std;

const int INT_MAX = 0x7fffffff;

map<char, int> add;
map<char, int> del;

void init() {
    add['1'] = 100;
    add['2'] = 200;
    add['3'] = 360;
    add['4'] = 220;
    del['1'] = 120;
    del['2'] = 350;
    del['3'] = 200;
    del['4'] = 320;
}

int main() {
    string str;
    cin >> str;
    init();
    int len = str.length();
    vector<vector<int> > dp(len + 1, vector<int>(len + 1, INT_MAX));
    for (int i = 0; i < len; ++i) dp[i][i] = 0;
    for (int i = 0; i < len - 1; ++i) {
        if (str[i] == str[i + 1])
            dp[i][i + 1] = 0;
        else {
            int minAdd = min(add[str[i]], add[str[i + 1]]);
            int minDel = min(del[str[i]], del[str[i + 1]]);
            dp[i][i + 1] = min(minAdd, minDel);
        }
    }
    for (int l = 2; l <= len; ++l) {
        for (int i = 0, j = l - i - 1; j < len; ++i, ++j) {
            if (str[i] == str[j])
                dp[i][j] = dp[i + 1][j - 1];
            else {
                int num1 = dp[i + 1][j - 1] + add[str[i]] + add[str[j]];
                int num2 = dp[i + 1][j - 1] + del[str[i]] + del[str[j]];
                int num3 = dp[i + 1][j - 1] + del[str[i]] + add[str[j]];
                int num4 = dp[i + 1][j - 1] + del[str[j]] + add[str[i]];
                int num5 = dp[i][j - 1] + min(add[str[j]], del[str[j]]);
                int num6 = dp[i + 1][j] + min(add[str[i]], del[str[i]]);
                dp[i][j] =
                    min(min(min(num1, num2), min(num3, num4)), min(num5, num6));
            }
        }
    }
    cout << dp[0][len - 1] << endl;
    return 0;
}

 

第二题

ab串 时间限制： 1000MS 内存限制： 65536KB 题目描述： 小明得到一个只包含a,b两个字符的字符串，但是小明不希望在这个字符串里a出现在b左边。现在他可以将”ab”这样的子串替换成”bba”，在原串中的相对位置不变。输出小明最少需要操作多少次才能让一个给定字符串所有a都在b的右边。


输入描述 一个只包含a,b字符的字符串，长度不超过100000。
输出描述 最小的操作次数。结果对1000000007取模。

样例输入 ab 样例输出 1
提示 样例1解释：ab到bba
样例2：
输入：aab
输出：3
样例2解释：aab到abba到bbaba到bbbbaa

 

思路：

　　做的时候就把这题当成一道数学题来做了，但是提交的时候只通过了45%，看别人的帖子说是因为count = 2 * count;这里没有取余。如果真的是因为没有取余造成的话感觉挺可惜的。

代码：

#include <iostream>
#include <string>

using namespace std;

int main() {
    string str;
    cin >> str;
    int numA = 0;
    int numB = 0;
    int len = str.length();
    int p1 = len - 1;
    int count = 0;
    while (p1 >= 0) {
        if (str[p1] == 'b') break;
        p1--;
    }
    while (p1 >= 0) {
        if (str[p1] == 'b')
            numB++;
        else {
            count = (count + numB) % 1000000007;
            numB = (2 * numB) % 1000000007;　　// 当时提交的时候这里没有取余
        }
        p1--;
    }
    cout << count << endl;
    return 0;
}