oyjpArt ACM/ICPC算法程序设计空间

// I am new in programming, welcome to my blog
I am oyjpart(alpc12, 四城)
posts - 224, comments - 694, trackbacks - 0, articles - 6
POJ

1716 Integer Intervals Accepted

1717 Dominoes Accepted

1718 River Crossing Accepted

1719 Shooting Contest Accepted

1720 SQUARES 不会做 几何题

1721 CARDS  Accepted

1722 SUBTRACT Accepted

1723 SOLDIERS Accepted

1725 BALL 好麻烦呀...

1731 Orders Accepted

1732 Phone numbers Accepted

dp[i]代表0->i的序列可以用字串组合的最小字串数 对每个i做n次转移 n是单词数

1733 Parity game  Accepted

1734 Sightseeing trip Accepted

1735 A Game on the Chessboard Accepted

1736 Block Town

Feedback

ym牛人
keke 来仰慕一下~

#include <algorithm>
using namespace std;
const int N = 10010;
int x[N], y[N];

int main() {
//freopen("t.in", "r", stdin);
int n, i;
scanf("%d", &n);
for(i = 0; i< n; i++)
scanf("%d%d", &x[i], &y[i]);
sort(x, x+n);
sort(y, y+n);
for(i = 0; i<n; i++)
x[i] -= i;
sort(x, x+n);
int ans = 0;
for(i = 0; i <n; i++)
ans += abs(x[i] - x[n/2]) + abs(y[i] - y[n/2]);
printf("%d\n", ans);
return 0;
}

#include <stdio.h>
#include <string.h>

const int N = 1010;
const int T = 2520;
const int MAXINT = 123456789;
int n;
int u[N], d[N];
bool dp[2][N];
int gcd[11][11];

int GCD(int a, int b) {
if(a < b) return GCD(b, a);
while(b != 0) {
int t = b;
b = a % b;
a = t;
}
return a;
}

inline int LCM(int a, int b) {
return a * b / GCD(a, b);
}

bool ok(int time, int i) {
int t = time % (u[i] + d[i]);
if(t == 0 || t > u[i]) return false;
return true;
}

int main() {
int ntc, i, t, j;
scanf("%d", &ntc);
while(ntc--) {
scanf("%d", &n);
int lcm = 1;
u[0] = u[n+1] = MAXINT; d[0] = d[n+1] = 0;
for(i = 1; i <= n; ++i) {
scanf("%d %d", &u[i], &d[i]);
lcm = LCM(lcm, u[i] + d[i]);
}
n += 2;
memset(dp, false, sizeof(dp));
dp[0][0] = 1;
for(t = 1; t <= lcm; ++t) {
int now = t % 2;
memset(dp[now], false, sizeof(dp[now]));
for(i = 0; i < n; ++i) if(ok(t, i)) {
for(j = i-5; j <= i+5; j++) if(j >= 0 && j < n) {
if(dp[!now][j]) { dp[now][i] = 1; break; }
}
}
if(dp[now][n-1]) { printf("%d\n", t); break; }
}
if(t > lcm) printf("NO\n");
}
return 0;
}

(0<=i-5<=j<=i+5<=n)就过啦。

我不是很明白，有讲这方面的资料吗？

谢谢了。。。。。。
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

const int N = 101;
struct Node {int x, w, f; void set(int xx, int ww, int ff) {x = xx; w = ww; f = ff;} };
int money, nv, ne;

bool operator<(const Node& a, const Node& b) { return a.w > b.w; }

void solve() {
int x, i, j, y;
priority_queue<Node> pq;
Node now, cur;
now.set(0, 0, 0);
pq.push(now);
while(!pq.empty()) {
cur = pq.top();
pq.pop();
x = cur.x;
if(x == nv-1) {
printf("%d\n", cur.w);
return;
}
for(i = 0; i < nv; ++i) {
for(j = 0; j < adj[x][i].size(); j++) if(cur.f + adj[x][i][j].f <= money) {
pq.push(now);
}
}
}
printf("-1\n");
}

int main() {
int i, u, v, w, f;
Node now;
scanf("%d %d %d", &money, &nv, &ne);
for(i = 0; i < ne; ++i) {
scanf("%d %d %d %d", &u, &v, &w, &f);
--u; --v;
now.set(v, w, f);
}

solve();

return 0;
}

Contact me via POJ mail : alpc12
email(MSN also) : yescrystalblue@sina.com

 只有注册用户登录后才能发表评论。 相关文章: