Codeforces Round #385 //再遇状压

敲完三题挂机一小时..... 也没懂DE什么意思 rank600上了一波分...

A. Hongcow Learns the Cyclic Shift

给一个字符串，每次可以把最后一个字符拿到开头问能形成多少种..

暴力模拟 set去重...

B. Hongcow Solves A Puzzle

判断矩形即可...

C. Hongcow Builds A Nation

并查集求最大块然后把未标记的块放进最大块里最后的连边数-最初的为我们添加的最多可能

D. Hongcow's Game

交互题第一次遇到 mk一下

E. Hongcow Buys a Deck of Cards

看不懂 ..... 特喵的又是个傻子状压..... 是时候总结一发状压特征了

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <vector>
#include <map>
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
pii make(int x,int y)
{
    return pii(x,y);
}
map<pii,int>dp[1<<17];
int n,r[20],b[20],c[20];
void UMAX(int& x,int y){if(x<y) x=y;};
void UMIN(int& x,int y){if(x>y) x=y;};
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        char ch[2];
        scanf("%s %d%d",ch,&r[i],&b[i]);
        if(ch[0]=='R') c[i] = 1;
    }
    dp[0][make(0,0)] = 0;
    map<pii,int>::iterator it;
    for(int x=0;x<(1<<n);x++)
    {
        int re = 0,bl = 0;
        for(int j=0;j<n;j++)if((x>>j)&1) c[j]?++re:++bl; 
        for(int j=0;j<n;j++)
        {
            if(x&(1<<j)) continue;
            for(it = dp[x].begin();it!=dp[x].end();it++)
            {
                int nxt = (1<<j)|x;
                int cnt = 0; //花费
                int rv = max(r[j]-re,0),bv = max(b[j]-bl,0);
                if(it->first.first<rv) UMAX(cnt,rv-it->first.first);
                if(it->first.second<bv) UMAX(cnt,bv-it->first.second);
                pii nxt_s = pii(it->first.first+cnt-rv,it->first.first+cnt-bv);
                if(dp[nxt].count(nxt_s)==0)dp[nxt][nxt_s] = INT_MAX;
                UMIN(dp[nxt][nxt_s],cnt+it->second+1);//1  为买操作
            }
        }
        
    }
    int ans = INT_MAX;
    for(it = dp[(1<<n)-1].begin();it!=dp[(1<<n)-1].end();it++)
    {
        UMIN(ans,it->second);
    }
    printf("%d
",ans);
    return 0;
}

AC代码