微软笔试3.25场讨论（附代码）

/*
1. 讨论去除不可行条件：1. N无法整除M，2. N中存在某个数字出现次数大于M
2. 对于可行条件，先排序，从小到大记录数字和其出现次数
3. 对于M个组，贪心生成每个组，从小到大选取还剩下的数字（每次选了数字，其剩余次数-1），具体为：
   1. 如果选够了N/M个数字，这组先保留；
   2. 如果没有选够，比如选了K个，还需要再选N/M - K个数字，则对于剩下的可选数字，一定和这一组的K个数字重复
   所以，我们把剩下的可选数字从小到大与前面选好的组进行元素置换，对于数字V：
   从下向上进行搜索（贪心），找到第一个不包含V的组，从后先前选取出第1个不在已选的K个数里的数字，置换这两个数
*/

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

struct prs {
    int val;
    int count;
};


bool preprocess(vector<int> &sco, vector<prs> &v, int M) {
    sort(sco.begin(), sco.end());
    prs ptmp;
    int i;
    ptmp.val = sco[0]-1;
    ptmp.count = 0;
    
    for(i = 0; i < sco.size(); i++) {
        if(ptmp.val != sco[i]) {
            if(i != 0) {
                if(ptmp.count > M) {
                    return 0;
                }
                v.push_back(ptmp);
            }
            ptmp.val = sco[i];
            ptmp.count = 1;
        }
        else {
            ptmp.count = ptmp.count + 1;
        }
    }
    v.push_back(ptmp);
    return 1;
}

bool find_val(vector<int> v, int val) {
    int l = 0, r = int(v.size() - 1);
    int mid;
    while(l <= r) {
        mid = (l+r)/2;
        if(v[mid] == val) {
            return 1;
        }
        else if(v[mid] > val){
            r = mid - 1;
        }
        else {
            l = mid + 1;
        }
    }
    return 0;
}

void single_step_up(vector<vector<int> > &grps, vector<int> &tmp, int val) {
    int i, j;
    bool flag = 0;
    for(i = int(grps.size()-1); i >= 0 && flag == 0; i--) {
        if(find_val(grps[i], val) == 0) {
            for(j = int(grps[i].size() - 1); j >= 0 && flag == 0; j--) {
                if(find_val(tmp, grps[i][j]) == 0) {
                    tmp.push_back(grps[i][j]);
                    grps[i].erase(grps[i].begin()+j, grps[i].begin()+j+1);
                    grps[i].push_back(val);
                    flag = 1;
                }
            }
        }
    }
    return;
}

void update(vector<vector<int> > &grps, vector<int> &tmp, vector<prs> &v) {
    int i, cc = 0;
    int steps = int(grps[0].size() - tmp.size());
    for(i = 0; i < steps; i++) {
        while(v[cc].count == 0) {
            cc++;
        }
        single_step_up(grps, tmp, v[cc].val);
        sort(tmp.begin(), tmp.end());
        v[cc].count--;
    }
    return;
}

int bestgroup(vector<int> &sco, int M) {
    if(sco.size()%M != 0) {
        return -1;
    }
    vector<prs> v;
    bool flag = preprocess(sco, v, M);
    if(flag == 0) {
        return -1;
    }
    vector<vector<int> > grps;
    vector<int> tmp;
    int sum = 0;
    
    int i,j,cc;
    for(i = 0; i < M; i++) {
        cc = 0;
        j = 0;
        while(tmp.size() < sco.size()/M && cc < v.size()) {
            if(v[cc].count != 0) {
                tmp.push_back(v[cc].val);
                v[cc].count = v[cc].count - 1;
            }
            cc++;
        }
        if(tmp.size() != sco.size()/M) {
            update(grps, tmp, v);
        }
        grps.push_back(tmp);
        
        tmp.clear();
    }
    
    for(i = 0; i < M; i++) {
        sum = sum + grps[i][sco.size()/M - 1] - grps[i][0];
    }
    return sum;
}

int main() {
    int N, M;
    cin>>N>>M;
    int stmp;
    vector<int> sco;
    int i;
    
    for(i = 0; i < N; i++) {
        cin>>stmp;
        sco.push_back(stmp);
    }
    
    cout<<bestgroup(sco, M)<<endl;
    return 0;
}

/*
 dp[i][j]表示第i~j位的字符串被消除需要的最小次数，则：
 如果s[i] != s[j]，那么dp[i][j] = min(dp[i][k] + dp[k+1][j]）
 如果s[i] == s[j]：dp[i][j]还有一种额外的情况 = dp[i+1][j-1] ，可以理解为最后一次满足回文直接消除
 也就是一定是可以分为两个分离的字符串段消除，求所有分离处理情况中最小的值
 （根据不同题意有两种情况，即偶数长度的回文是否可以一次消除，会影响不同的初始化条件，本代码假设可以）
 */

#include<iostream>
using namespace std;

int minelim(string s1) {
    if(s1.length() <= 1) {
        return s1.length();
    }
    int dp[s1.length()][s1.length()];
    int i, j, k;
    
    for(i = 0; i < s1.length(); i++) {
        dp[i][i] = 1;
    }
    for(i = 0; i < s1.length()-1; i++) {
        if(s1[i] == s1[i+1]) {
            dp[i][i+1] = 1;
        }
        else {
            dp[i][i+1] = 2;
        }
    }
    
    for(i = 2; i < s1.length(); i++) {
        for(j = 0; i+j < s1.length(); j++) {
            if(s1[j] == s1[i+j]) {
                dp[j][i+j] = dp[j+1][i+j-1];
            }
            else {
                dp[j][i+j] = i+1;
            }
            for(k = j; k < i+j; k++) {
                dp[j][i+j] = min(dp[j][i+j], dp[j][k] + dp[k+1][i+j]);
            }
        }
    }
    
    return dp[0][s1.length()-1];
}

int main() {
    string s1;
    cin>>s1;
    cout<<minelim(s1)<<endl;
}