yaleyaledaze

392

yaleyaledaze
2个月前

#include <algorithm>
#include <iostream>

using namespace std;

const int N = 100010;

int n;
int a[N];
int q[N];

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

int len = 0;
for (int i = 0; i < n; i++)
{
int  pos = len;
pos = lower_bound(q + 1, q + len + 1, a[i]) - (q + 1);
len = max(len, pos + 1);
q[pos + 1] = a[i];
}

cout << len << endl;

return 0;
}

int len=0;
q[0]=-1e9;//因为有负值，第0个数还是要设一个最小值
for(int i=0;i<n;i++){
int l=0,r=len+1;//左闭右开
while(l<r){
int mid=l+r>>1;
if(q[mid]>=a[i]) r=mid;
else l=mid+1;
}
len=max(len,l);//这里r和l都可以，因为左闭右开保证能进入while循环
q[l]=a[i];
}
printf("%d\n",len);

yaleyaledaze
2个月前
#include <algorithm>
#include <iostream>

using namespace std;

const int N = 100010;

int n;
int a[N];
int q[N];

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

int len = 0;
for (int i = 0; i < n; i++)
{
int  pos = len;
pos = lower_bound(q + 1, q + len + 1, a[i]) - (q + 1);
len = max(len, pos + 1);
q[pos + 1] = a[i];
}

cout << len << endl;

return 0;
}

yaleyaledaze
2个月前
#include <bits/stdc++.h>

using namespace std;

const int N = 310;

int n;
int s[N];
int f[N][N];

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

for (int i = 1; i <= n; i++)
s[i] += s[i - 1];

for (int len = 2; len <= n; len++)
for (int i = 1; i + len - 1 <= n; i++)
{
int l = i, r = i + len - 1;
f[l][r] = 1e9;
for (int k = l; k < r; k++)
f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]);
}

cout << f[1][n] << endl;
return 0;
}

yaleyaledaze
3个月前
#include <bits/stdc++.h>
using namespace std;

const int N = 1010;
int f[N][N];
char a[N], b[N];

int main()
{
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++)
cin >> a[i];
for (int i = 1; i <= m; i++)
cin >> b[i];

for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
{
f[i][j] = max(f[i - 1][j], f[i][j - 1]);
if (a[i] == b[j])
f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1);
}
cout << f[n][m] << endl;
return 0;
}

yaleyaledaze
3个月前

### 题目描述

input:
3 5
2
1 2
2 4
1
3 4
1
4 5
output:
8

#### C++ 代码

f[i,j]=max(f[i-1][j],f[i-1,j-v[i,k]]+w[i,k])

#include <bits/stdc++.h>

using namespace std;

const int N = 110;
int f[N][N], s[N], v[N][N], w[N][N];

int main()
{
int m, n;
cin >> m >> n; //m=N,n=V

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

wa了个痛快！

#include <bits/stdc++.h>

using namespace std;

const int N = 110;
int f[N][N], s[N], v[N][N], w[N][N];

int main()
{
int m, n;
cin >> m >> n; //m=N,n=V

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

for(int k=0;k<=s[i]&&v[i][k]<=j;k++)

v[i] [k]关于k并不是递增的，所以当前的k不满足要求，并不意味着后面的k也不满足要求，不能结束循环，应该改成：

if(j >= v[i][k]) f[i][j] = max(f[i][j], f[i - 1][j - v[i][k]] + w[i][k]);

f[i][j] = max(f[i-1][j], f[i][j]);

#include <bits/stdc++.h>

using namespace std;

const int N = 110;
int f[N], s[N], v[N][N], w[N][N];

int main()
{
int m, n;
cin >> m >> n; //m=N,n=V

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

yaleyaledaze
3个月前
#include <bits/stdc++.h>
using namespace std;

const int N = 1010;
int a[N], f[N];

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

for (int i = 1; i <= n; i++)
{
f[i] = 1;
for (int j = 1; j < i; j++)
if (a[j] < a[i])
f[i] = max(f[i], f[j] + 1);
res = max(res, f[i]);
}

cout << res << endl;
return 0;
}

yaleyaledaze
3个月前
#include <bits/stdc++.h>
using namespace std;

const int N = 510;
int a[N][N];

int main()
{
int n, ans = 0;
cin >> n;
memset(a,-0x37,sizeof(a));
for (int i = 1; i <= n; i++)
for (int j = 1; j <= i; j++)
cin >> a[i][j];

for (int i = 2; i <= n; i++)
for (int j = 1; j <= i; j++)
a[i][j] += max(a[i - 1][j - 1], a[i - 1][j]);
for (int i = 1; i <= n;i++)
ans = max(ans, a[n][i]);
cout << ans << endl;
//system("pause");
return 0;
}

yaleyaledaze
3个月前

f[i,j]=max(f[i-1][j],f[i-1,j-v[i,k]]+w[i,k])

#include <bits/stdc++.h>

using namespace std;

const int N = 110;
int f[N][N], s[N], v[N][N], w[N][N];

int main()
{
int m, n;
cin >> m >> n; //m=N,n=V

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

wa了个痛快！

#include <bits/stdc++.h>

using namespace std;

const int N = 110;
int f[N][N], s[N], v[N][N], w[N][N];

int main()
{
int m, n;
cin >> m >> n; //m=N,n=V

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

for(int k=0;k<=s[i]&&v[i][k]<=j;k++)

v[i] [k]关于k并不是递增的，所以当前的k不满足要求，并不意味着后面的k也不满足要求，不能结束循环，应该改成：

if(j >= v[i][k]) f[i][j] = max(f[i][j], f[i - 1][j - v[i][k]] + w[i][k]);

f[i][j] = max(f[i-1][j], f[i][j]);

#include <bits/stdc++.h>

using namespace std;

const int N = 110;
int f[N], s[N], v[N][N], w[N][N];

int main()
{
int m, n;
cin >> m >> n; //m=N,n=V

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

yaleyaledaze
3个月前
#include <bits/stdc++.h>

using namespace std;

const int N = 110;
int f[N][N], s[N], v[N][N], w[N][N];

int main()
{
int m, n;
cin >> m >> n; //m=N,n=V

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

yaleyaledaze
3个月前
#include <bits/stdc++.h>

using namespace std;

const int N = 12010, M = 2010;

int n, m;
int v[N], w[N];
int f[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] = a * k;
w[cnt] = b * k;
s -= k;
k *= 2;
}
if (s > 0)   //剩余部分
{
cnt ++ ;
v[cnt] = a * s;
w[cnt] = b * s;
}
}

n = cnt;

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

cout << f[m] << endl;

//system("pause");

return 0;
}