模板

快读

1. inline int read()
2. {
3.         int x = 0;
4.         int flag = 1;
5.         char c = getchar();
6.         while(!isdigit(c))
7.         {
8.                 if(c == '-')
9.                 flag = -1;
10.                 c = getchar();
11.         }
12.         while(isdigit(c))
13.         {
14.                 x = x * 10 + (c - '0');
15.                 c = getchar();
16.         }
17.         return x * flag;
18. }//快读

复制代码

1. template<typename T> void read(T&x)
2. {
3.         char c;int sign = 1;x = 0;
4.         // 判断是否是负数，以及去掉前面多余的字符
5.         do { c = getchar(); if(c == '-') sign = -1; }while(!isdigit(c));
6.         do { x = x * 10 + c - '0'; c = getchar(); }while(isdigit(c));
7.         x *= sign;
8. }

复制代码

快出

1. inline void put(long long d)
2. {
3.         if(d < 0)
4.         putchar('-'),d = -d;
5.         if(d > 9) put(d / 10);
6.     putchar((d % 10) + '0');
7. }

复制代码

dp

LIS 和 LCS

最长上升子序列(LIS)

[code]#includeusing namespace std;const int N = 1e5 + 50;long long s[N],top;long long a[N],ans,n,ma = -1;int main(){        cin >> n;        for(int i = 1;i > a;        for(int i = 1;i  a;        s[++ top] = a[1];        for(int i = 2;i = a)                        s[left_boundary(a)] = a;                else                s[++ top] = a;        }        cout n;        for(int i=1;i>a;                c[a]=i;        }        for(int i=1;i>b;        }        dp[1]=c[b[1]];        int k=1;        for(int i=2;idp[k])                {                        k++;                        dp[k]=c[b];                }                else                {                        dp[lower_bound(dp+1,dp+1+k,c[b])-dp]=c[b];                }        }        couts;        for(int i=1;i>w>>v;        }        for(int i=1;i=w;j--)                {                        dp[j]=max(dp[j],dp[j-w]+v);                }        }        coutn>>s;        for(int i=1;i>w>>v;                for(int j=w;j>c;        for(int i=1;i>wi>>vi>>shu;                k = 1;                while(shu>=k)                {                        q ++;                        v[q] = vi*k;                        w[q] = wi*k;                        shu -= k;                        k *= 2;                }                if(shu>0)                {                        q++;                        v[q] = vi*shu;                        w[q] = wi*shu;                }                        }        for(int i=1;i=w;j--)        dp[j]=max(dp[j],dp[j-w]+v);        cout n >> c;        for(int i = 1;i > wi >> vi >> si;                if(si > 0)                {                        int t=1;                        while(t>vk>>wk;        for(int i = 1;i >v >>w >>s;                for(int j = vk;j >= v;j --)                        for(int k = wk;k >= w;k --)                        dp[j][k]=max(dp[j][k],dp[j - v][k - w] + s);        }                        cout v second -> w        int m = read(),n = read();        for(int i = 1;i = q.second)                                        dp[j] = max(dp[j],dp[j - a.w] + a.v - q.first);                                else                                        dp[j] = max(dp[j],dp[j - a.w] + a.v);                        }                        else                        {                                dp[j] = max(dp[j],dp[j - a.w] + a.v);                                o.push_back(make_pair(a.group,make_pair(a.v,a.w)));                        }                 }         }                        cout >n>>m>>s;        for(int i=1;i>x>>y>>c;                add(x,y,c);        }        dij();        for(int i=1;i>y>>c;                add(x,y,c);        }        dij(s);        for(int i=1;i m >> s;        int x,y,k;        for(int i = 1;i > x >> y >> k;                add(x,y,k);        }        for(int i = 1;i m;        for(int i=1;i>x>>y>>w;                dp[x][y]=min(dp[x][y],w);//可能存在重边                 dp[y][x]=min(dp[y][x],w);        }        for(int i=1;i