2022-09-14
摘花生
#include <bits/stdc++.h>
using namespace std;
const double pi = acos(-1);
const double eps=1e-7;
const int base=132;
#define YES cout<<"YES"<<endl
#define NO cout<<"NO"<<endl
#define x first
#define y second
#define int long long
#define lb long double
#define pb push_back
#define endl '\n'//交互题删掉此
#define all(v) (v).begin(),(v).end()
#define PII pair<int,int>
#define rep(i,x,n) for(int i=x;i<=n;i++)
#define dwn(i,n,x) for(int i=n;i>=x;i--)
#define ll_INF 0x7f7f7f7f7f7f7f7f
#define INF 0x3f3f3f3f
#define debug(x) cerr << #x << ": " << x << endl
#define io ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
int Mod(int a,int mod){return (a%mod+mod)%mod;}
int lowbit(int x){return x&-x;}//最低位1及其后面的0构成的数值
int qmi(int a, int k, int p){int res = 1 % p;while (k){if (k & 1) res = Mod(res * a , p);a = Mod(a * a , p);k >>= 1;}return res;}
int inv(int a,int mod){return qmi(a,mod-2,mod);}
int n,m;
const int N=1010;
int g[N][N];
int f[N][N];
void solve()
{
cin>>n>>m;
memset(f,0,sizeof f);
rep(i,1,n)
rep(j,1,m)
cin>>g[i][j];
rep(i,1,n)
{
rep(j,1,m)
{
if(i==1&&j==1)f[i][j]=g[i][j];
else if(i==1)f[i][j]=max(f[i][j],f[i][j-1]+g[i][j]);
else if(j==1)f[i][j]=max(f[i][j],f[i-1][j]+g[i][j]);
else f[i][j]=max(f[i-1][j],f[i][j-1])+g[i][j];
}
}
cout<<f[n][m]<<endl;
}
signed main()
{
io;
int _;_=1;
cin>>_;
while(_--)solve();
return 0;
}
最低交通费用
#include <bits/stdc++.h>
using namespace std;
const double pi = acos(-1);
const double eps=1e-7;
const int base=132;
#define YES cout<<"YES"<<endl
#define NO cout<<"NO"<<endl
#define x first
#define y second
#define int long long
#define lb long double
#define pb push_back
#define endl '\n'//交互题删掉此
#define all(v) (v).begin(),(v).end()
#define PII pair<int,int>
#define rep(i,x,n) for(int i=x;i<=n;i++)
#define dwn(i,n,x) for(int i=n;i>=x;i--)
#define ll_INF 0x7f7f7f7f7f7f7f7f
#define INF 0x3f3f3f3f
#define debug(x) cerr << #x << ": " << x << endl
#define io ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
int Mod(int a,int mod){return (a%mod+mod)%mod;}
int lowbit(int x){return x&-x;}//最低位1及其后面的0构成的数值
int qmi(int a, int k, int p){int res = 1 % p;while (k){if (k & 1) res = Mod(res * a , p);a = Mod(a * a , p);k >>= 1;}return res;}
int inv(int a,int mod){return qmi(a,mod-2,mod);}
int n,m;
const int N=1010;
int g[N][N];
int f[N][N];
void solve()
{
cin>>n;
rep(i,1,n)
rep(j,1,n)
cin>>g[i][j];
memset(f,0x3f,sizeof f);
rep(i,1,n)
rep(j,1,n)
{
if(i==1&&j==1)f[i][j]=g[i][j];
else if(i==1)f[i][j]=min(f[i][j],f[i][j-1]+g[i][j]);
else if(j==1)f[i][j]=min(f[i][j],f[i-1][j]+g[i][j]);
else f[i][j]=min(f[i-1][j],f[i][j-1])+g[i][j];
}
cout<<f[n][n]<<endl;
}
signed main()
{
io;
int _;_=1;
//cin>>_;
while(_--)solve();
return 0;
}
方格取数
#include <bits/stdc++.h>
using namespace std;
const double pi = acos(-1);
const double eps=1e-7;
const int base=132;
#define YES cout<<"YES"<<endl
#define NO cout<<"NO"<<endl
#define x first
#define y second
#define int long long
#define lb long double
#define pb push_back
#define endl '\n'//交互题删掉此
#define all(v) (v).begin(),(v).end()
#define PII pair<int,int>
#define rep(i,x,n) for(int i=x;i<=n;i++)
#define dwn(i,n,x) for(int i=n;i>=x;i--)
#define ll_INF 0x7f7f7f7f7f7f7f7f
#define INF 0x3f3f3f3f
#define debug(x) cerr << #x << ": " << x << endl
#define io ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
int Mod(int a,int mod){return (a%mod+mod)%mod;}
int lowbit(int x){return x&-x;}//最低位1及其后面的0构成的数值
int qmi(int a, int k, int p){int res = 1 % p;while (k){if (k & 1) res = Mod(res * a , p);a = Mod(a * a , p);k >>= 1;}return res;}
int inv(int a,int mod){return qmi(a,mod-2,mod);}
int n;
const int N=15;
int g[N][N];
int f[2*N][N][N];
void solve()
{
cin>>n;
int a,b,c;
while(cin>>a>>b>>c,a||b||c)g[a][b]=c;
rep(k,2,2*n)
{
rep(i1,1,n)
{
rep(i2,1,n)
{
int j1=k-i1,j2=k-i2;
if(j1<1||j1>n||j2<1||j2>n)continue;
int &x=f[k][i1][i2];
int t=g[i1][j1];
if(i1!=i2)t+=g[i2][j2];
x=max(x,f[k-1][i1-1][i2-1]+t);
x=max(x,f[k-1][i1-1][i2]+t);
x=max(x,f[k-1][i1][i2-1]+t);
x=max(x,f[k-1][i1][i2]+t);
}
}
}
cout<<f[n*2][n][n]<<endl;
}
signed main()
{
io;
int _;_=1;
//cin>>_;
while(_--)solve();
return 0;
}
传纸条
#include <bits/stdc++.h>
using namespace std;
const double pi = acos(-1);
const double eps=1e-7;
const int base=132;
#define YES cout<<"YES"<<endl
#define NO cout<<"NO"<<endl
#define x first
#define y second
#define int long long
#define lb long double
#define pb push_back
#define endl '\n'//交互题删掉此
#define all(v) (v).begin(),(v).end()
#define PII pair<int,int>
#define rep(i,x,n) for(int i=x;i<=n;i++)
#define dwn(i,n,x) for(int i=n;i>=x;i--)
#define ll_INF 0x7f7f7f7f7f7f7f7f
#define INF 0x3f3f3f3f
#define debug(x) cerr << #x << ": " << x << endl
#define io ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
int Mod(int a,int mod){return (a%mod+mod)%mod;}
int lowbit(int x){return x&-x;}//最低位1及其后面的0构成的数值
int qmi(int a, int k, int p){int res = 1 % p;while (k){if (k & 1) res = Mod(res * a , p);a = Mod(a * a , p);k >>= 1;}return res;}
int inv(int a,int mod){return qmi(a,mod-2,mod);}
int n,m;
const int N=55;
int g[N][N];
int f[2*N][N][N];
void solve()
{
cin>>n>>m;
rep(i,1,n)
rep(j,1,m)
cin>>g[i][j];
rep(k,2,n+m)
{
rep(i1,1,n)
{
rep(i2,1,n)
{
int j1=k-i1,j2=k-i2;
if(j1<1||j1>m||j2<1||j2>m)continue;
int &x=f[k][i1][i2];
int t=g[i1][j1];
if(i1!=i2)t+=g[i2][j2];
x=max(x,f[k-1][i1-1][i2-1]+t);
x=max(x,f[k-1][i1-1][i2]+t);
x=max(x,f[k-1][i1][i2-1]+t);
x=max(x,f[k-1][i1][i2]+t);
}
}
}
cout<<f[n+m][n][n]<<endl;
}
signed main()
{
io;
int _;_=1;
//cin>>_;
while(_--)solve();
return 0;
}
怪盗基德的滑翔翼
#include <bits/stdc++.h>
using namespace std;
const double pi = acos(-1);
const double eps=1e-7;
const int base=132;
#define YES cout<<"YES"<<endl
#define NO cout<<"NO"<<endl
#define x first
#define y second
#define int long long
#define lb long double
#define pb push_back
#define endl '\n'//交互题删掉此
#define all(v) (v).begin(),(v).end()
#define PII pair<int,int>
#define rep(i,x,n) for(int i=x;i<=n;i++)
#define dwn(i,n,x) for(int i=n;i>=x;i--)
#define ll_INF 0x7f7f7f7f7f7f7f7f
#define INF 0x3f3f3f3f
#define debug(x) cerr << #x << ": " << x << endl
#define io ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
int Mod(int a,int mod){return (a%mod+mod)%mod;}
int lowbit(int x){return x&-x;}//最低位1及其后面的0构成的数值
int qmi(int a, int k, int p){int res = 1 % p;while (k){if (k & 1) res = Mod(res * a , p);a = Mod(a * a , p);k >>= 1;}return res;}
int inv(int a,int mod){return qmi(a,mod-2,mod);}
int n,m;
const int N=110;
int h[N],f[N];
void solve()
{
cin>>n;
rep(i,1,n)cin>>h[i];
int res=0;
rep(i,1,n)
{
f[i]=1;
rep(j,1,i-1)
if(h[j]<h[i])f[i]=max(f[i],f[j]+1);
res=max(res,f[i]);
}
memset(f,0,sizeof f);
dwn(i,n,1)
{
f[i]=1;
dwn(j,n,i+1)
if(h[j]<h[i])f[i]=max(f[i],f[j]+1);
res=max(res,f[i]);
}
cout<<res<<endl;
}
signed main()
{
io;
int _;_=1;
cin>>_;
while(_--)solve();
return 0;
}
登山
#include <bits/stdc++.h>
using namespace std;
const double pi = acos(-1);
const double eps=1e-7;
const int base=132;
#define YES cout<<"YES"<<endl
#define NO cout<<"NO"<<endl
#define x first
#define y second
#define int long long
#define lb long double
#define pb push_back
#define endl '\n'//交互题删掉此
#define all(v) (v).begin(),(v).end()
#define PII pair<int,int>
#define rep(i,x,n) for(int i=x;i<=n;i++)
#define dwn(i,n,x) for(int i=n;i>=x;i--)
#define ll_INF 0x7f7f7f7f7f7f7f7f
#define INF 0x3f3f3f3f
#define debug(x) cerr << #x << ": " << x << endl
#define io ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
int Mod(int a,int mod){return (a%mod+mod)%mod;}
int lowbit(int x){return x&-x;}//最低位1及其后面的0构成的数值
int qmi(int a, int k, int p){int res = 1 % p;while (k){if (k & 1) res = Mod(res * a , p);a = Mod(a * a , p);k >>= 1;}return res;}
int inv(int a,int mod){return qmi(a,mod-2,mod);}
int n,m;
const int N=1010;
int h[N],f[N],g[N];
void solve()
{
cin>>n;
rep(i,1,n)cin>>h[i];
rep(i,1,n)
{
f[i]=1;
rep(j,1,i-1)
if(h[i]>h[j])f[i]=max(f[i],f[j]+1);
}
dwn(i,n,1)
{
g[i]=1;
dwn(j,n,i+1)
if(h[i]>h[j])g[i]=max(g[i],g[j]+1);
}
int res=0;
rep(i,1,n)res=max(res,f[i]+g[i]-1);
cout<<res<<endl;
}
signed main()
{
io;
int _;_=1;
//cin>>_;
while(_--)solve();
return 0;
}
2022-9-16
合唱队伍
#include <bits/stdc++.h>
using namespace std;
const double pi = acos(-1);
const double eps=1e-7;
const int base=132;
#define YES cout<<"YES"<<endl
#define NO cout<<"NO"<<endl
#define x first
#define y second
#define int long long
#define lb long double
#define pb push_back
#define endl '\n'//交互题删掉此
#define all(v) (v).begin(),(v).end()
#define PII pair<int,int>
#define rep(i,x,n) for(int i=x;i<=n;i++)
#define dwn(i,n,x) for(int i=n;i>=x;i--)
#define ll_INF 0x7f7f7f7f7f7f7f7f
#define INF 0x3f3f3f3f
#define debug(x) cerr << #x << ": " << x << endl
#define io ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
int Mod(int a,int mod){return (a%mod+mod)%mod;}
int lowbit(int x){return x&-x;}//最低位1及其后面的0构成的数值
int qmi(int a, int k, int p){int res = 1 % p;while (k){if (k & 1) res = Mod(res * a , p);a = Mod(a * a , p);k >>= 1;}return res;}
int inv(int a,int mod){return qmi(a,mod-2,mod);}
int n;
const int N=110;
int a[N];
int f[N],g[N];
void solve()
{
cin>>n;
rep(i,1,n)cin>>a[i];
rep(i,1,n)
{
f[i]=1;
rep(j,1,i-1)
if(a[i]>a[j])f[i]=max(f[i],f[j]+1);
}
dwn(i,n,1)
{
g[i]=1;
dwn(j,n,i+1)
if(a[i]>a[j])g[i]=max(g[i],g[j]+1);
}
int res=0;
rep(i,1,n)
res=max(res,f[i]+g[i]);
cout<<n-res+1<<endl;
}
signed main()
{
io;
int _;_=1;
//cin>>_;
while(_--)solve();
return 0;
}
友好城市
#include <bits/stdc++.h>
using namespace std;
const double pi = acos(-1);
const double eps=1e-7;
const int base=132;
#define YES cout<<"YES"<<endl
#define NO cout<<"NO"<<endl
#define x first
#define y second
#define int long long
#define lb long double
#define pb push_back
#define endl '\n'//交互题删掉此
#define all(v) (v).begin(),(v).end()
#define PII pair<int,int>
#define rep(i,x,n) for(int i=x;i<=n;i++)
#define dwn(i,n,x) for(int i=n;i>=x;i--)
#define ll_INF 0x7f7f7f7f7f7f7f7f
#define INF 0x3f3f3f3f
#define debug(x) cerr << #x << ": " << x << endl
#define io ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
int Mod(int a,int mod){return (a%mod+mod)%mod;}
int lowbit(int x){return x&-x;}//最低位1及其后面的0构成的数值
int qmi(int a, int k, int p){int res = 1 % p;while (k){if (k & 1) res = Mod(res * a , p);a = Mod(a * a , p);k >>= 1;}return res;}
int inv(int a,int mod){return qmi(a,mod-2,mod);}
int n;
const int N=5010;
int f[N];
void solve()
{
cin>>n;
vector<PII>v;
rep(i,1,n)
{
int a,b;
cin>>a>>b;
v.pb({a,b});
}
sort(all(v));
int res=0;
rep(i,0,n-1)
{
f[i]=1;
rep(j,0,i-1)
if(v[i].y>v[j].y)f[i]=max(f[i],f[j]+1);
res=max(res,f[i]);
}
cout<<res<<endl;
}
signed main()
{
io;
int _;_=1;
//cin>>_;
while(_--)solve();
return 0;
}
最大上升子序列和
#include <bits/stdc++.h>
using namespace std;
const double pi = acos(-1);
const double eps=1e-7;
const int base=132;
#define YES cout<<"YES"<<endl
#define NO cout<<"NO"<<endl
#define x first
#define y second
#define int long long
#define lb long double
#define pb push_back
#define endl '\n'//交互题删掉此
#define all(v) (v).begin(),(v).end()
#define PII pair<int,int>
#define rep(i,x,n) for(int i=x;i<=n;i++)
#define dwn(i,n,x) for(int i=n;i>=x;i--)
#define ll_INF 0x7f7f7f7f7f7f7f7f
#define INF 0x3f3f3f3f
#define debug(x) cerr << #x << ": " << x << endl
#define io ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
int Mod(int a,int mod){return (a%mod+mod)%mod;}
int lowbit(int x){return x&-x;}//最低位1及其后面的0构成的数值
int qmi(int a, int k, int p){int res = 1 % p;while (k){if (k & 1) res = Mod(res * a , p);a = Mod(a * a , p);k >>= 1;}return res;}
int inv(int a,int mod){return qmi(a,mod-2,mod);}
int n;
const int N=1010;
int f[N];
int a[N];
void solve()
{
cin>>n;
rep(i,1,n)cin>>a[i];
int res=0;
rep(i,1,n)
{
f[i]=a[i];
rep(j,1,i-1)
if(a[i]>a[j])f[i]=max(f[i],f[j]+a[i]);
res=max(res,f[i]);
}
cout<<res<<endl;
}
signed main()
{
io;
int _;_=1;
//cin>>_;
while(_--)solve();
return 0;
}
拦截导弹
#include <bits/stdc++.h>
using namespace std;
const double pi = acos(-1);
const double eps=1e-7;
const int base=132;
#define YES cout<<"YES"<<endl
#define NO cout<<"NO"<<endl
#define x first
#define y second
#define int long long
#define lb long double
#define pb push_back
#define endl '\n'//交互题删掉此
#define all(v) (v).begin(),(v).end()
#define PII pair<int,int>
#define rep(i,x,n) for(int i=x;i<=n;i++)
#define dwn(i,n,x) for(int i=n;i>=x;i--)
#define ll_INF 0x7f7f7f7f7f7f7f7f
#define INF 0x3f3f3f3f
#define debug(x) cerr << #x << ": " << x << endl
#define io ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
int Mod(int a,int mod){return (a%mod+mod)%mod;}
int lowbit(int x){return x&-x;}//最低位1及其后面的0构成的数值
int qmi(int a, int k, int p){int res = 1 % p;while (k){if (k & 1) res = Mod(res * a , p);a = Mod(a * a , p);k >>= 1;}return res;}
int inv(int a,int mod){return qmi(a,mod-2,mod);}
int n;
const int N=1010;
int f[N];
int a[N];
void solve()
{
while(cin>>a[n])n++;
int res=0;
int cnt=0;
vector<int>v(n);
dwn(i,n-1,0)
{
f[i]=1;
dwn(j,n-1,i+1)
if(a[i]>=a[j])f[i]=max(f[i],f[j]+1);
res=max(res,f[i]);
int k=0;
while(k<cnt&&a[i]<v[k])k++;
if(k==cnt)v[cnt++]=a[i];
else v[k]=a[i];
}
cout<<res<<endl;
cout<<cnt<<endl;
}
signed main()
{
io;
int _;_=1;
//cin>>_;
while(_--)solve();
return 0;
}
牛