模板

厂潺 · 4 天前

快读

inline int read()
{
int x = 0;
int flag = 1;
char c = getchar();
while(!isdigit(c))
{
if(c == '-')
flag = -1;
c = getchar();
}
while(isdigit(c))
{
x = x * 10 + (c - '0');
c = getchar();
}
return x * flag;
}//快读

复制代码

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

复制代码

快出

inline void put(long long d)
{
if(d < 0)
putchar('-'),d = -d;
if(d > 9) put(d / 10);
putchar((d % 10) + '0');
}

复制代码

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

账号		自动登录	找回密码
密码			立即注册