#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N=20,M=1<<N;

int f[M][N],w[N][N];//w表示的是无权图

int main()
{
    int n;
    cin>>n;

    for(int i=0;i<n;i++)
     for(int j=0;j<n;j++)
      cin>>w[i][j];

    memset(f,0x3f,sizeof(f));//因为要求最小值，所以初始化为无穷大
    f[1][0]=0;//因为零是起点,所以f[1][0]=0;

    for(int i=0;i<1<<n;i++)//i表示所有的情况
     for(int j=0;j<n;j++)//j表示走到哪一个点
      if(i>>j&1)
       for(int k=0;k<n;k++)//k表示走到j这个点之前,以k为终点的最短距离
        if(i>>k&1)
         f[i][j]=min(f[i][j],f[i-(1<<j)][k]+w[k][j]);//更新最短距离

    cout<<f[(1<<n)-1][n-1]<<endl;//表示所有点都走过了,且终点是n-1的最短距离
    //位运算的优先级低于'+'-'所以有必要的情况下要打括号
    return 0;
}

#include<iostream>
#include<cstring>

using namespace std;

//数据范围1~11
const int N = 12;
//每一列的每一个空格有两种选择，放和不放，所以是2^n
const int M = 1 << N;
//方案数比较大，所以要使用long long 类型
//f[i][j]表示 i-1列的方案数已经确定，从i-1列伸出，并且第i列的状态是j的所有方案数
long long f[N][M];
//第 i-2 列伸到 i-1 列的状态为 k ， 是否能成功转移到 第 i-1 列伸到 i 列的状态为 j
//st[j|k]=true 表示能成功转移
bool st[M];
//n行m列
int n, m;

int main() {
//    预处理st数组
    while (cin >> n >> m, n || m) {
        for (int i = 0; i < 1 << n; i++) {
//            第 i-2 列伸到 i-1 列的状态为 k ， 
//            能成功转移到 
//            第 i-1 列伸到 i 列的状态为 j
            st[i] = true;
//            记录一列中0的个数
            int cnt = 0;
            for (int j = 0; j < n; j++) {
//                通过位操作，i状态下j行是否放置方格，
//                0就是不放， 1就是放
                if (i >> j & 1) {
//                    如果放置小方块使得连续的空白格子数成为奇数，
//                    这样的状态就是不行的，
                    if (cnt & 1) {
                        st[i] = false;
                        break;
                    }
                }
                else cnt++;
//                不放置小方格
            }

            if (cnt & 1) st[i] = false;
        }

//        初始化状态数组f
        memset(f, 0, sizeof f);

//        棋盘是从第0列开始，没有-1列，所以第0列第0行，不会有延伸出来的小方块
//        没有横着摆放的小方块，所有小方块都是竖着摆放的，这种状态记录为一种方案
        f[0][0] = 1;
//        遍历每一列
        for (int i = 1; i <= m; i++) {
//            枚举i列每一种状态
            for (int j = 0; j < 1 << n; j++) {
//                枚举i-1列每一种状态
                for (int k = 0; k < 1 << n; k++) {
//                    f[i-1][k] 成功转到 f[i][j]
                    if ((j & k) == 0 && st[j | k]) {
                        f[i][j] += f[i - 1][k]; //那么这种状态下它的方案数等于之前每种k状态数目的和
                    }
                }
            }
        }
//        棋盘一共有0~m-1列
//        f[i][j]表示 前i-1列的方案数已经确定，从i-1列伸出，并且第i列的状态是j的所有方案数
//        f[m][0]表示 前m-1列的方案数已经确定，从m-1列伸出，并且第m列的状态是0的所有方案数
//        也就是m列不放小方格，前m-1列已经完全摆放好并且不伸出来的状态
        cout << f[m][0] << endl;
    }
    return 0;
}

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int N = 5e4 + 5;
PII a[N];
int main()
{
    int n;
    cin >> n;
    for(int i = 0; i < n; i ++ )
    {
        int x, y;
        scanf("%d %d", &x, &y);
        a[i].first = x + y;
        a[i].second = y;
    }
    sort(a, a + n);
    ll res = -1e18, sum = 0;
    for(int i = 0; i < n; i ++ )
    {
        sum -= a[i].second;
        res = max(res, sum);
        sum += a[i].first;
    }
    cout << res << endl;
    return 0;
}

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

    sort(a,a+n);
    int res=0;
    for(int i=0;i<n/2;i++){
        res+=a[n-i-1]-a[i];
    }

    cout<<res;
}

#include<iostream>
#include<algorithm>
using namespace std;
int n;
int a[100010];
int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }

    sort(a,a+n);
    long long res=0;
    for(int i=0;i<n;i++){
        res+=a[i]*(n-i-1);
    }
     cout<<res;
    return 0;
}

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

int main(){
    int n;
    cin>>n;
    priority_queue<int,vector<int>,greater<int>> heap;

    while(n--) {
        int x;
        cin>>x;
        heap.push(x);
    }

    int res=0;
    while(heap.size()>1){
        int a=heap.top(); heap.pop();
        int b=heap.top(); heap.pop();
        res+=a+b;
        heap.push(a+b);
    }

    cout<<res;
    return 0;
}

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

int n;
struct Range
{
    int l, r;
    bool operator< (const Range &W)const
    {
        return l < W.l;
    }
}range[N];

int main()
{
    int st, ed;
    scanf("%d%d", &st, &ed);
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ )
    {
        int l, r;
        scanf("%d%d", &l, &r);
        range[i] = {l, r};
    }

    sort(range, range + n);

    int res = 0;
    bool success = false;
    for (int i = 0; i < n; i ++ )
    {
        int j = i, r = -2e9;
        while (j < n && range[j].l <= st)
        {
            r = max(r, range[j].r);
            j ++ ;
        }

        if (r < st)
        {
            res = -1;
            break;
        }

        res ++ ;
        if (r >= ed)
        {
            success = true;
            break;
        }

        st = r;
        i = j - 1;
    }

    if (!success) res = -1;
    printf("%d\n", res);

    return 0;
}

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100100;

int n;
int b[2 * N], idx;

int main()
{
    scanf ("%d", &n);
    for(int i = 0; i < n; i ++)
    {
        int l, r;
        scanf("%d %d", &l, &r);
        b[idx ++] = l * 2;//标记左端点为偶数。
        b[idx ++] = r * 2 + 1;// 标记右端点为奇数。
    }

    sort(b, b + idx);

    int res = -3, t = 0;
    for(int i = 0; i < idx; i ++)
    {
        if(b[i] % 2 == 0) t ++;
        else t --;
        res = max(res, t);
    }
    printf ("%d\n", res);
    return 0;
}

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

int n;
struct Range
{
    int l, r;
    bool operator< (const Range &W)const
    {
        return r < W.r;
    }
}range[N];

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) scanf("%d%d", &range[i].l, &range[i].r);

    sort(range, range + n);

    int res = 0, ed = -2e9;
    for (int i = 0; i < n; i ++ )
        if (ed < range[i].l)
        {
            res ++ ;
            ed = range[i].r;
        }

    printf("%d\n", res);

    return 0;
}

算法思路

用右端点排序，然后每当发现下面的某个区间左端点在当前考察区间右端点右边，就更新
可理解为：按右端点从小到大排序是因为这样可以只考虑当前考虑的区间的右端点，因为后面的区间的的右端点一定在此区间的右边，不会无缘无故被迫更新。

基于这种思路，考虑下面这两个题的联系

1.上题的正确性约束是此题的最值（要求最大）约束

上题要求每个区间都要被选到，所以每当下面没了的时候必须加点；
此题要求最大值，下面都没了还不立刻选下面的区间，那就不能保证最大了

2.此题的正确性约束是上题的最值（要求最小）约束

上题要求尽可能少地选点，故只要和现在考察的区间有交集，就不加新的点
此题要求区间不相交，故只要能和现在考察的区间有交集，都不能选

综合就是，当且仅当发现下面的某个区间左端点在当前考察区间右端点右面，一定更新，保证正确性和最值

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

int n;
struct Range
{
    int l, r;
    bool operator< (const Range &W)const
    {
        return r < W.r;
    }
}range[N];

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) scanf("%d%d", &range[i].l, &range[i].r);

    sort(range, range + n);

    int res = 0, ed = -2e9;
    for (int i = 0; i < n; i ++ )
        if (ed < range[i].l)
        {
            res ++ ;
            ed = range[i].r;
        }

    printf("%d\n", res);

    return 0;
}