#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 20, M = 1<<N;
int g[N][N],f[M][N];
int n;
int main(){
    cin>>n;
    for(int i = 0 ; i < n ; i ++)
        for(int j = 0 ; j < n ; j++)
            cin>>g[i][j];
    memset(f,0x3f,sizeof f);
    f[1][0] = 0;
    for(int i = 1 ; i < 1<<n ; i++){
        for(int j = 0 ; j < n ; j ++){
            if(i>>j & 1){
                for(int k = 0 ; k < n ; k++){
                    if(i>>k & 1)
                        f[i][j] = min(f[i][j],f[i-(1<<j)][k]+g[k][j]);
                }
            }
        }
    }
            cout<<f[(1<<n)-1][n-1]<<endl;
            return 0;
}

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
const int N = 12, M = 1<<N;
typedef long long ll;
ll f[N][M];
vector<int> state[M];
bool st[M];
int n,m;
int main(){
    while(cin>>n>>m,n||m){
        //预处理1：看看哪些状态有连续奇数个0，标记一下，这些状态是不合法的，合法的状态标记为true
        for(int i = 0 ; i < 1<<n ; i++){
            int cnt = 0;
            bool isValid = true;
            for(int j = 0;j < n;j++){
                if(i>>j & 1){
                    if(cnt & 1){
                        isValid = false;
                        break;
                    }
                    cnt = 0;
                }else cnt++;
            }
            if(cnt & 1) isValid = false;
            st[i] = isValid;
        }
            //预处理2：看看哪些状态是真正的合法的状态，把他们装进state，state[j]存储的是能转移到状态j的合法状态
            for(int i = 0;i < 1<<n ; i++){
                state[i].clear();
                for(int j = 0; j < 1<<n;j++){
                    if((i&j) == 0 && st[i | j]){
                        state[i].push_back(j);
                    }
                }
            }
            //开始dp
            memset(f,0,sizeof f);
            f[0][0] = 1;
            for(int i = 1; i <= m; i++){
                for(int j = 0 ; j < 1<<n ; j++){
                    for(auto k:state[j])
                        f[i][j]+=f[i-1][k];
                }
            }

            cout<<f[m][0]<<endl;
        }
        return 0;
    }

状态压缩的思想：把状态压缩在一个二进制数里，常常用于表示元素是否在集合中，在则用1 ， 不在则用0.

#include <iostream>
#include <algorithm>
using namespace std;
const int N =5e4+10;
typedef long long ll;
typedef pair<int,int> pii;
pii cows[N];
int main(){
    int n;
    cin>>n;
    for(int i = 0 ; i < n ; i++){
        int w,s;
        cin>>w>>s;
        cows[i] = {w+s,s};
    }
    sort(cows,cows+n);
    ll sum = 0;
    ll res = -2e9;
    for(int i = 0 ; i < n ; i++){
        int s = cows[i].second,w = cows[i].first - s;
        ll risk = sum - s;
        res = max(res,risk);
        sum += w;
    }
    cout<<res<<endl;
    return 0;
}

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 1e5+10;
int a[N];
typedef long long ll;
ll res;
int main(){
    int n;
    cin>>n;
    for(int i = 0;i < n;i++) cin>>a[i];

    sort(a,a+n);

    int x = a[n/2];

    for(int i = 0;i < n;i++) res += abs(a[i]-x);

    cout<<res<<endl;
    return 0;
}

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5+10;
typedef long long ll;
int t[N];
int n;
ll res;
int main(){
    cin>>n;
    for(int i = 1 ; i <= n;i++)cin>>t[i];

    sort(t+1,t+n+1);

    for(int i = 1;i<=n;i++) res+=(n-i)*t[i];

    cout<<res<<endl;

    return 0;
}

提示：证明用调整法

#include <iostream>
#include <queue>
using namespace std;
int main(){
    int n;
    cin>>n;

    priority_queue<int,vector<int>,greater<int>> heap;

    while(n--){
        int a;
        cin>>a;
        heap.push(a);
    }
    int res = 0;
    while(heap.size()>1){
        int t = heap.top();
        heap.pop();
        t+=heap.top();
        res += t;
        heap.pop();
        heap.push(t);
    }
    cout<<res<<endl;
    return 0;
}

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5+10;
typedef pair<int,int> pii;
pii range[N];
int main(){
    int st,ed;
    cin>>st>>ed;
    int n;
    cin>>n;
    for(int i = 0;i < n;i++){
        int a,b;
        cin>>a>>b;
        range[i] = {a,b};
    }
    sort(range,range + n);
    bool success = false;
    int res = 0;
    for(int i = 0; i < n ; i++){
        int r = -2e9;
        int j = i;
        while(j<n && range[j].first <= st){
            r = max(r,range[j].second);
            j++;
        }

        if(r < st){
            success = false;
            break;
        }
        res++;
        if(r >= ed){
            success = true;
            break;
        }
        i = j-1;
        st = r;
    }
    if(success) cout<<res<<endl;
    else cout<<-1<<endl;
    return 0;
}

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
const int N = 1e5+10;
typedef pair<int,int> pii;
pii range[N];
int n;
int main(){
    cin>>n;
    for(int i = 0; i < n;i++){
        int l,r;
        cin>>l>>r;
        range[i]={l,r};
    }
    sort(range,range+n);
    priority_queue<int,vector<int>,greater<int>> heap;
    for(int i = 0; i < n;i++){
        pii r = range[i];
        if(heap.empty() || r.first <= heap.top()){
            heap.push(r.second);
        }else{
            heap.pop();
            heap.push(r.second);
        }
    }
    cout<<heap.size()<<endl;
    return 0;
}

与上一题：区间选点的联系

本题的代码与上一题：区间选点完全相同。本题要求的是最大不相交区间的数量，而我们来看看区间选点的题目要求：选择尽量少的点，使得每个区间内至少有一个点。在这题的条件要求下，最少的点数，其实就是本题的最大不相交的区间数。因为对于这组区间里的每个区间，都至少要放一个点来覆盖这个区间。

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

typedef pair<int,int> pii;

vector<pii> all;

bool cmp(pii &a,pii &b){
    return a.second < b.second;
}
int main(){
    int n;
    cin>>n;
    while(n--){
        int a,b;
        cin>>a>>b;
        all.push_back({a,b});
    }
    sort(all.begin(),all.end(),cmp);
    int res = 0, ed = -2e9;
    for(auto t:all){
        if(t.first > ed){
            res++;
            ed = t.second;
        }
    }

    cout<<res<<endl;

    return 0;
}

主要思路

贪心想法：按照右端点排序之后，选区间的右端点相较于选其他点更优，更能覆盖到更多区间。

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

typedef pair<int,int> pii;

vector<pii> all;

bool cmp(pii &a,pii &b){
    return a.second < b.second;
}
int main(){
    int n;
    cin>>n;
    while(n--){
        int a,b;
        cin>>a>>b;
        all.push_back({a,b});
    }
    sort(all.begin(),all.end(),cmp);
    int res = 0, ed = -2e9;
    for(auto t:all){
        if(t.first > ed){
            res++;
            ed = t.second;
        }
    }

    cout<<res<<endl;

    return 0;
}