oyjpArt ACM/ICPC算法程序設計空間

ym牛人

keke 來仰慕一下~

能說一下那個1723號題中,你說對X方向上,對每個坐標減去所在位置,是什么意思?

貼下代碼，可能容易理解些~
#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;
}

請問1718那道題目是不是:
先對所有a+b求最大公約數，得到最大時間t1。然后在這段時間內做DP （a[t][i]代表t時刻i地址是否可達），每次檢查a[t-1][j](0<=i-5<=j<=i-1)是否可達，有一個可達則a[t][i]可達。
請賜教啊，WA了好多次了。。。

你參考下源代碼吧，如果還WA，我們QQ說。 :)
#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;
}

呵呵，參考你的源碼，終于AC啦。
原來沒有考慮過了橋墩可以跳回來的情況，所以條件改為
(0<=i-5<=j<=i+5<=n)就過啦。

1724 roads 雙調路徑能說進更詳細些嗎？

　　　我不是很明白，有講這方面的資料嗎？

　　　　　　　　　　　謝謝了。。。。。。

1724 roads的代碼：
#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;} };
vector<Node> adj[N][N];
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) {
y = adj[x][i][j].x;
now.set(y, cur.w + adj[x][i][j].w, cur.f + adj[x][i][j].f);
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);
adj[u][v].push_back(now);
}

solve();

return 0;
}

能留個聯系方式嗎？ 最近也在為ACM努力著。 有不懂的，希望你能幫我！

謝謝了。。。

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

暈。。。您一天能切多少題。。。

額。。這個說不定啊。。除了比賽一般不超過5道啦。。