246

23小时前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 310;
int n,m;
int h[N][N];
int f[N][N];

int dx[4] = {-1, 0, 1, 0},dy[4] = {0, 1, 0, -1};

int dfs(int x,int y) {
if(f[x][y] != -1) return f[x][y];

f[x][y] = 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])
f[x][y] = max(f[x][y],dfs(a,b) + 1);
}
return f[x][y];
}

int main() {
cin >> n >> m;

for(int i = 1;i <= n;i++)
for(int j = 1;j <= m;j++)
cin >> h[i][j];

memset(f,-1,sizeof f);

int res = 0;
for(int i = 1;i <= n;i++)
for(int j = 1;j <= m;j++)
res = max(res,dfs(i,j));

cout << res << endl;

return 0;
}

2天前
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int get(vector<int> nums,int l,int r) {
int res = 0;
for(int i = l;i >= r;i--) res = res * 10 + nums[i];
return res;
}

int power(int x) {
int res = 1;
while(x--) res *= 10;
return res;
}

int count(int n,int x) {
if(!n) return 0;

vector<int> nums;
while(n) {
nums.push_back(n % 10);
n /= 10;
}
n = nums.size();

int res = 0;
for(int i = n - 1 - !x;i >= 0;i--) {
if(i < n - 1) {
res += get(nums,n - 1,i + 1) * power(i);
if(!x) res -= power(i);
}
if(x == nums[i]) res += get(nums,i - 1,0) + 1;
else if(x < nums[i]) res += power(i);
}
return res;
}

int main() {
int a,b;
while(cin >> a >> b,a || b) {
if(a > b) swap(a,b);
for(int i = 0;i < 10;i++)
cout << count(b,i) - count(a - 1,i) << " ";
cout << endl;
}
return 0;
}

2天前
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 6010;
int happy[N];
int h[N],e[N],ne[N],idx;
int f[N][2];
bool has_father[N];

e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}

int dfs(int u) {
f[u][1] = happy[u];

for(int i = h[u];i != -1;i = ne[i]) {
int j = e[i];
dfs(j);

f[u][0] += max(f[j][0],f[j][1]);
f[u][1] += f[j][0];
}
}

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

memset(h,-1, sizeof h);

for(int i = 0;i < n - 1;i++) {
int a,b;
cin >> a >> b;
has_father[a] = true;
}

int root = 1;
while(has_father[root]) root++;

dfs(root);

cout << max(f[root][0],f[root][1]) << endl;

return 0;
}

4天前
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 20,M = 1 << N;
int n;
int w[N][N];
//f[i][j]集合：所有的 从0到j的所有路径
//属性：最小值
int f[M][N];

int main() {
cin >> n;

for(int i = 0;i < n;i++)
for(int j = 0;j < n;j++)
cin >> w[i][j];

memset(f,0x3f,sizeof f);
f[0][0] = 0;

for(int i = 0;i < 1 << n;i++)
for(int j = 1;j < n;j++)
if(i >> j & 1)
for(int k = 1;k < n;k++)
if(i >> k & 1)
f[i][j] = min(f[i][j],f[i -(1 << j)][k] + w[k][j]);

cout << f[(1 << n) - 1][n - 1] << endl;

return 0;
}

4天前
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;
int n,m;
int p[N];

int find(int x) {
if(x != p[x]) p[x] = find(p[x]);
return p[x];
}

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

while(m--) {
char op[2];
int a,b;
scanf("%s",op);
if(*op == 'M') {
cin >> a >> b;
p[find(a)] = find(b);
}
else {
cin >> a >> b;
if(p[find(a)] == p[find(b)]) puts("Yes");
else puts("No");
}
}

return 0;
}

4天前
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110;
int n,m;
int s[N],v[N][N],w[N][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;
}

4天前
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;
int n,m;
int v[N],w[N];
int f[N];

int main() {
cin >> n >> m;

for(int i = 1;i <= n;i++) cin >> v[i] >> w[i];

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

cout << f[m] << endl;

return 0;
}

5天前
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;
int n,m;
int v[N],w[N];
int f[N];

int main() {
cin >> n >> m;

for(int i = 1;i <= n;i++) cin >> v[i] >> w[i];

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;
}

6天前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 12,M = 1 << N;
int n,m;
long long f[N][M];
bool st[M];

int main() {
while(cin >> n >> m,n | m) {
//预处理所以的状态
for(int i = 0;i < 1 << n;i++) {
int cnt = 0;
st[i] = true;
for(int j = 0;j < n;j++)
if(i >> j & 1) {
if(cnt & 1) st[i] = false;
cnt = 0;
}
else cnt++;
if(cnt & 1) st[i] = false;
}

memset(f,0,sizeof f);
f[0][0] = 1;

//m列,第一列的摆法只有一种
//第m + 1列,也就是下标为m的列表示前面的所有的方法数
for(int i = 1;i <= m;i++)
for(int j = 0;j < 1 << n;j++)
for(int k = 0;k < 1 << n;k++)
if((j & k) == 0 && st[j | k])
f[i][j] += f[i - 1][k];
cout << f[m][0] << endl;
}

return 0;
}

8天前
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010,mod = 1e9 + 7;
int n;
//集合：所有的 前i个数,和恰好为j的方法的集合
//属性：个数
int f[N];

int main() {
cin >> n;

f[0] = 1;
for(int i = 1;i <= n;i++)
for(int j = i;j <= n;j++)
f[j] = (f[j] + f[j - i]) % mod;

cout << f[n] << endl;

return 0;
}