当前位置：文档之家 › ACM题目与答案—A

ACM题目与答案—A

  • 格式：doc
  • 大小：558.50 KB
  • 文档页数：16

下载文档原格式

  / 35
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

目录

水果沙拉 (1)

拆铁路 (4)

神奇宝贝 (8)

生日party (11)

屠龙宝镜 (14)

水果沙拉

#include

#include

const int MAX_N = 100;

const int MAX_A = 100;

const int MAX_B = 100;

const int MAX_V = 2 * MAX_N * MAX_A;

int max(int a, int b) {

return a > b ? a : b;

}

int main()

{

int dp[MAX_V];

int a[MAX_N];

int b[MAX_N];

int i,j, n, k;

scanf("%d %d", &n, &k);

int offset = n * MAX_A;

int v = 2 * offset;

for (i = 0; i < n; ++i)

{

scanf("%d", &a[i]);

}

for (i = 0; i < n; ++i)

{

scanf("%d", &b[i]);

b[i] = a[i] - k*b[i];

}

memset(dp, -1, sizeof(dp));

dp[offset] = 0;

for (i = 0; i < n; ++i)

{

bool isMinus = b[i] < 0;

if (isMinus)

{

for (j = 0; j < v + b[i]; ++j)

{

if (dp[j - b[i]] != -1)

{

dp[j] = max(dp[j], dp[j - b[i]] + a[i]);

}

}

}

else

{

for (j = v - 1; j >= b[i]; --j)

{

if (dp[j - b[i]] != -1)

{

dp[j] = max(dp[j], dp[j - b[i]] + a[i]);

}

}

}

}

printf("%d\n", dp[offset]==0?-1: dp[offset]);

return 0;

}

拆铁路

#include #include #include

#include

#include

#include

#include

#include

#include

#include

#include

#include

#define maxn 10001

#define INF 1e17

typedef __int64 LL;

using namespace std;

struct Edge

{

LL from, to, dist;

};

struct node

{

LL d, u;

bool operator < (const node &a) const { return a.d

}

};

struct Dijstra

{

LL n, m;

priority_queue q;

node tmp, now;

Edge e;

vector edges;

vector G[maxn];

bool done[maxn];

LL dis[maxn];

LL in[maxn];

void init(void)

{

edges.clear();

memset(in, 0, sizeof in);

memset(done, 0, sizeof done);

for(int i = 0; i < maxn; i++)

G[i].clear();

}

void addedge(int from, int to, int dist)

{

e.from = from, e.to = to, e.dist = dist;

edges.push_back(e);

m = edges.size();

G[from].push_back(m-1);

}

void dijstra(int s)

{

for(int i = 0; i <= n; i++) dis[i] = INF;

dis[s] = 0;

tmp.u = s, tmp.d = 0;

q.push(tmp);

while(!q.empty()) {

now = q.top();

q.pop();

if(done[now.u]) continue;

done[now.u] = true;

int d = G[now.u].size();

for(int i = 0; i < d; i++) {

Edge& e = edges[G[now.u][i]];

if(dis[e.to] == dis[now.u] + e.dist)

in[e.to]++;

if(dis[e.to] > dis[now.u] + e.dist) {

dis[e.to] = dis[now.u] + e.dist;

in[e.to] = 1;

tmp.u = e.to, tmp.d = dis[e.to];

q.push(tmp);

}

}

}

}

}tmp;

struct opr

{

LL v, dist;

}op[maxn];

void debug(void)

{

for(int i = 1; i <= tmp.n; i++) {

printf("%I64d\n", tmp.in[i]);

}

}

int main(void)

{

相关主题