夢追い人

"It takes a dreamer to make a dream come true."―Vincent Willem van Gogh

DP練とかJOI練とか

とりあえずコードだけね。
反省点とかもありますが・・・

0535

#include <cstdio>
#include <algorithm>
using namespace std;
int m, n;
int maps[92][92];
int res;
void dfs(int x, int y, int r) {
	int dx[] = {-1,0,0,1};
	int dy[] = {0,-1,1,0};
	maps[x][y]=0;
	for (int i=0; i<4; i++) {
		int nx=x+dx[i],ny=y+dy[i];
		if (maps[nx][ny]) {
			dfs(nx,ny,r+1);
		}
	}
	res=max(r,res);
	maps[x][y]=1;
}
int main() {
	while (scanf("%d%d",&m,&n)) {
		if (m==0&&n==0) break;
		for (int i=1; i<=n; i++) for (int j=1; j<=m; j++)
			scanf("%d",&maps[i][j]);
		res = 0;
		for (int i=1; i<=n; i++) for (int j=1; j<=m; j++) {
			if (maps[i][j]) {
				dfs(i,j,0);
			}
		}
		printf("%d\n",res+1);
	}
}

0168

#include <cstdio>
typedef long long ll;
int main() {
	int n;
	ll dp[30];
	dp[0]=1; dp[1]=2; dp[2]=4;
	for (int i=3; i<30; i++) dp[i]=dp[i-3]+dp[i-2]+dp[i-1];
	while (scanf("%d",&n)) {
		if (n==0) break;
		ll day,year;
		if (dp[n-1]%10!=0) day=dp[n-1]/10+1;
		else day=dp[n-1]/10;
		if (day%365!=0) year=day/365+1;
		else year=day/365;
		printf("%lld\n",year);
	}
}

0557

#include <cstdio>
typedef long long ll;
int main() {
	int n; scanf("%d",&n);
	int r, num[n];
	for (int i=0; i<n-1; i++) scanf("%d",&num[i]);
	scanf("%d",&num[n-1]);
	ll dp[n-1][21];
	for (int i=0; i<n-1; i++) for (int j=0; j<21; j++) dp[i][j]=0;
	dp[0][num[0]]=1;
	for (int i=1; i<n-1; i++) {
		for (int j=0; j<21; j++) {
			if (j+num[i]<21) dp[i][j]+=dp[i-1][j+num[i]];
			if (j-num[i]>=0) dp[i][j]+=dp[i-1][j-num[i]];
		}
	}	
	printf("%lld\n",dp[n-2][num[n-1]]);
}

0042

#include <cstdio>
#include <map>
#include <algorithm>
using namespace std;
typedef pair<int, int> P;
int main() {
	int w,n,c=1;
	while (scanf("%d",&w)) {
		if (w==0) break;
		scanf("%d",&n);
		int W[n],V[n];
		for (int i=0; i<n; i++) scanf("%d%*c%d",&V[i],&W[i]);
		int dp[n+1][w+1];
		int rw=1001,rv=0;
		for (int i=0; i<=w; i++) dp[n][i]=0;
		for (int i=n-1; i>=0; i--) {
			for (int j=0; j<=w; j++) {
				if (W[i]>j) dp[i][j]=dp[i+1][j];
				else {
					int r1=dp[i+1][j],r2=dp[i+1][j-W[i]]+V[i];
					if (r2>=r1) {
						if (rv<r2) {
							rv=r2;
							rw=j;
						} else if (rv==r2) {
							rw=min(rw,j);
						}
						dp[i][j]=r2;
					} else {
						dp[i][j]=r1;
					}
				}
			}
		}
		printf("Case %d:\n%d\n%d\n",c++,rv,rw);
	}
}
広告を非表示にする