tzz1011

3520

tzz1011
6天前

tzz1011
8天前
#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
using namespace std;

const int N = 310;
int h[N][N];
int f[N][N];
int n, m;
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

int dp(int x, int y)
{
int &v = f[x][y];
if(v != -1) return v;//这个点走过的话直接返回这个点的值

v = 1;
for(int i = 0; i < 4; i++)
{
int a = x + dx[i], b = y + dy[i];
if(a >= 1 && a <= n && b >= 1 && b <= m && h[a][b] < h[x][y])
{
v = max(v, dp(a, b) + 1);
}
}

return v;
}
int main()
{
scanf("%d %d", &n, &m);

memset(f, -1, sizeof(f));

for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
scanf("%d", &h[i][j]);
}
}

int ans = 0;
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
ans = max(ans, dp(i, j));
}
}

printf("%d\n", ans);
return 0;
}


tzz1011
1个月前
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1010;
int n, m;
char a[N], b[N];
int f[N][N];

int main()
{
scanf("%d%s", &n, a + 1);
scanf("%d%s", &m, b + 1);

for (int i = 0; i <= m; i++) f[0][i] = i; //a的0个字母与b的前i个字母比较
for (int i = 0; i <= n; i++) f[i][0] = i; //a的前i个字母与b的0个字母比较

for(int i = 1; i<= n; i++)
for (int j = 1; j <= m; j++)
{
f[i][j] = min(f[i - 1][j] + 1, f[i][j - 1] + 1);
if (a[i] == b[j]) f[i][j] = min(f[i][j], f[i - 1][j - 1]);
else f[i][j] = min(f[i][j], f[i - 1][j - 1] + 1);
}

printf("%d\n", f[n][m]);
return 0;
}


tzz1011
1个月前
#include<iostream>
#include<algorithm>
using namespace std;
const int  N = 110;
int n, m;
int v[N][N], w[N][N], s[N];
int f[N];

int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
cin >> s[i];
for (int j = 0; j < s[i]; j++)
{
cin >> v[i][j] >> w[i][j];
}
}

for (int i = 1; i <= n; i++)
for (int j = m; j > 0; j--)
for (int k = 0; k < s[i]; k++)
if (v[i][k] <= j)
f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
cout << f[m] << endl;
return 0;
}


tzz1011
1个月前

#### 版本一

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 100010;
int n;
int q[N], a[N];

int main()
{
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i];

int len = 0;
q[0] = -2e9;
for (int i = 0; i < n; i++)
{
int l = 0, r = len;
while (l < r)
{
int mid = l + r + 1 >> 1;//相当于（l + r + 1) / 2;
cout << mid << endl;
if (q[mid] < a[i]) l = mid;
else r = mid - 1;
}
len = max(len, r + 1);
q[r + 1] = a[i];

cout << len << " " << a[i] << endl;
}

cout << len << endl;
system("pause");
return 0;
}


#### 版本二

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

int main()
{
int n;
cin >> n;
vector<int> a(n);
vector<int> q;
for (int i = 0; i < n; i++) cin >> a[i];

q.push_back(a[0]);//模拟堆栈
for (int i = 1; i < n; i++)
{
if (a[i] > q.back()) q.push_back(a[i]);
else
*lower_bound(q.begin(), q.end(), a[i]) = a[i];
}

cout << q.size() << endl;
return 0;
}


tzz1011
2个月前

#include<iostream>
#include<algorithm>
using namespace std;
const int N=20000;
int f[N];
int v[N],w[N];
int n,m;
int main()
{
cin >> n >> m;
int cnt = 0;
for(int i = 1;i <= n;i ++)
{
int a,b,s;
cin >> a >> b >> s;
int k = 1;
while(k <= s)
{
cnt ++;
v[cnt] = k * a;
w[cnt] = k * b;
s -= k;
k *= 2;
}
if(s > 0)
{
cnt ++;
v[cnt] = s * a;
w[cnt] = s * b;
}
}

n = cnt;

for(int i = 1; i <= n; i ++)
for(int j = m; j >= v[i]; j --)
f[j] = max(f[j],f[j - v[i]] + w[i]);

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


tzz1011
2个月前

、、、

# include[HTML_REMOVED]

using namespace std;
const int N=20000;
int f[N];
int v[N],w[N];
int n,m;
int main()
{
cin >> n >> m;
int cnt = 0;
for(int i = 1;i <= n;i )
{
int a,b,s;
cin >> a >> b >> s;
int k = 1;
while(k <= s)
{
cnt
;
v[cnt] = k * a;
w[cnt] = k * b;
s -= k;
k *= 2;
}
if(s > 0)
{
cnt ++;
v[cnt] = s * a;
w[cnt] = s * b;
}
}

n = cnt;

for(int i = 1; i <= n; i ++)
for(int j = m; j >= v[i]; j --)
f[j] = max(f[j],f[j - v[i]] + w[i]);

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


}
、、、

tzz1011
2个月前
#include<iostream>
#include<cstring>

using namespace std;

const int N=1e5+3;
int e[N],q[N],ne[N],idx;

void insert(int tmp){
int k=(tmp%N+N)%N;
e[idx]=tmp,ne[idx]=q[k],q[k]=idx++;
}

int find(int tmp){
int k=(tmp%N+N)%N;
for(int i=q[k];i!=-1;i=ne[i])
if(e[i]==tmp)
return true;

return false;
}

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

memset(q,-1,sizeof q);

int t;
while(n--){
cin>>op;
cin>>t;
if(op=="I"){
insert(t);
}
else {
find(t)?cout<<"Yes":cout<<"No";
cout<<endl;
}
}
return 0;
}


tzz1011
3个月前
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

vector<int> E[5010];
int n, m;
int dfn[5010], low[5010], timestamp;
int stk[5010], top;
int id[5010], dcc_cnt;
vector<pair<int, int>> brige;
int du[5010];

void tarjan(int u, int fa)
{
dfn[u] = low[u] = ++ timestamp;
stk[++ top] = u;
for (int i = 0; i < E[u].size(); i ++)
{
int v = E[u][i];
if (!dfn[v])
{
tarjan(v, u);
low[u] = min(low[u], low[v]);
if (low[v] > dfn[u])
brige.push_back({u, v});
}
else if (v != fa)
low[u] = min(low[u], dfn[v]);
}

if (dfn[u] == low[u])
{
dcc_cnt ++;
int y;
do {
y = stk[top --];
id[y] = dcc_cnt;

} while (y != u);
}
}

int main()
{
cin >> n >> m;
for (int i = 0; i < m; i ++)
{
int a, b;
cin >> a >> b;
E[a].push_back(b);
E[b].push_back(a);
}

tarjan(1, -1);

for (auto x : brige)
{
int a = x.first, b = x.second;
du[id[a]] ++, du[id[b]] ++;
}

int cnt = 0;
for (int i = 1; i <= dcc_cnt; i ++)
cnt += (du[i] == 1);

cout << (cnt + 1) / 2 << endl;

return 0;
}


tzz1011
4个月前
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std;

const int N = 101;
vector<int> E[N], DAGE[N];
int dfn[N], low[N], timestamp;
stack<int> stk;
bool instk[N];
int color[N];
int cnt;
int chu[N], ru[N];

int n;

void tarjan(int u)
{
dfn[u] = low[u] = ++ timestamp;
stk.push(u);
instk[u] = true;
for (int i = 0; i < E[u].size(); i ++)
{
int v = E[u][i];
if (!dfn[v])
{
tarjan(v);
low[u] = min(low[u], low[v]);
}
else if (instk[v])
low[u] = min(low[u], dfn[v]);
}

if (low[u] == dfn[u])
{
cnt ++;
while (1)
{
int v = stk.top();
stk.pop();
instk[v] = false;
color[v] = cnt;
if (v == u) break;
}
}

}

int main()
{
cin >> n;
for (int i = 1; i <= n; i ++)
{
int x;
while (1)
{
cin >> x;
if (x == 0) break;
E[i].push_back(x);
}
}

for (int i = 1; i <= n; i ++)
if (!dfn[i])
tarjan(i);

for (int i = 1; i <= n; i ++)
{
for (int j = 0; j < E[i].size(); j ++)
{
int v = E[i][j];
if (color[i] != color[v])
{
DAGE[color[i]].push_back(color[v]);
ru[color[v]] ++;
chu[color[i]] ++;
}
}
}

int c = 0, r = 0;
for (int i = 1; i <= cnt; i ++)
{
if (!chu[i]) c ++;
if (!ru[i]) r ++;
}

cout << r << endl;

if (cnt == 1)
cout << 0 << endl;
else
cout << max(r, c) << endl;

return 0;
}