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

ACM题目与答案—A

水果沙拉 (1)

拆铁路 (4)

神奇宝贝 (8)

生日party (11)

屠龙宝镜 (14)

水果沙拉

#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

#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)

{

LL m, k, u, v, dist, ans = 0;

scanf("%I64d%I64d%I64d", &tmp.n, &m, &k);

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

scanf("%I64d%I64d%I64d", &u, &v, &dist);

tmp.addedge(u, v, dist);

tmp.addedge(v, u, dist);

}

for(i = 0; i < k ; i++) {

scanf("%I64d%I64d", &op[i].v, &op[i].dist);

tmp.addedge(1, op[i].v, op[i].dist);

}

tmp.dijstra(1);

for(i = 0; i < k; i++) {

if(op[i].dist == tmp.dis[op[i].v]) if(tmp.in[op[i].v] > 1) ans++, tmp.in[op[i].v]--;

if(op[i].dist > tmp.dis[op[i].v]) ans++;

}

printf("%I64d\n", ans);

return 0;

}

神奇宝贝

#include #include

#define N_MAX 1005 class Point

{

public:

int row;

int col;

Point(int row, int col):row(row), col(col){}

};

int N, M, i, j, eRow, eCol, row, col, total = 0;

char map[N_MAX][N_MAX], ch;

int visited[N_MAX][N_MAX];

bool reached;

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

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

int main() {

scanf("%d%d", &N, &M);

for (i = 1; i <= N; i++) {

scanf("%s", &map[i][1]);

for (j = 1; j <= M; j++) {

if (map[i][j] == 'E') {

eRow = i; eCol = j;

}

std::vector level;

std::vector nextLevel;

level.push_back(Point(eRow, eCol));

visited[eRow][eCol] = 1;

while (!reached) {

nextLevel.clear();

for (i = 0; i < level.size(); i++) {

Point p = level[i];

for (j = 0; j < 4; j++) {

row = p.row + rb[j];

col = p.col + cb[j];

if (row < 1 || row > N) continue;

if (col < 1 || col > M) continue;

if (map[row][col] == 'T') continue;

if (map[row][col] == 'S') { reached = 1; continue; }

if (visited[row][col]) continue;

nextLevel.push_back(Point(row, col));

visited[row][col] = 1;

}

for (i = 0; i < nextLevel.size(); i++) {

Point p2 = nextLevel[i];

total += map[p2.row][p2.col] - '0';

//printf("(%d,%d %d) ", p2.row, p2.col, map[p2.row][p2.col] - '0');

}

//printf("\n");

level = nextLevel;

}

printf("%d\n", total);

return 0;

}

生日party

#include

using namespace std;

const int maxn=105;

int max(int a,int b){ return a>b?a:b; }

struct Node {

int a,b;

bool operator < (const Node& x) const {

return b

}

} ns[maxn];

struct Heap {

int cur,val,vol,cnt,up;

Heap(int cur,int val,int vol,int cnt,int up):cur(cur),val(val),vol(vol),cnt(cnt),up(up) {} bool operator < (const Heap& hp) const {

return up

}

Heap() {}

};

int n;

int sumv[maxn],dp[maxn][maxn];

int main() {

int i,j;

scanf("%d",&n);

int suma=0;

for(i=1; i<=n; i++) {

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

suma+=ns[i].a;

}

for(i=1; i<=n; i++) scanf("%d",&ns[i].b);

sort(ns+1,ns+n+1);

int sumb=0;

for(i=n; i>=1&&suma>sumb; i--) {

sumb+=ns[i].b;

} //k 代表最少瓶数

int k=n-i;

sumv[0]=0;

for(i=1; i<=n; i++) sumv[i]=sumv[i-1]+ns[i].b;

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

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

dp[i][0]=0;

for(j=1; j<=i; j++) {

dp[i][j]=max(dp[i-1][j-1]+ns[i].a,dp[i-1][j]);

}

int res=0;

priority_queue pq;

pq.push(Heap(n,0,0,0,dp[n][k]));

while(!pq.empty()) {

Heap u=pq.top();

pq.pop();

if(https://www.doczj.com/doc/ba17738243.html,t==k){

res=u.up;

break;

}

//没儿子

int cur_vol=u.vol+sumv[u.cur]-sumv[u.cur-(https://www.doczj.com/doc/ba17738243.html,t)];

int lef_cnt=https://www.doczj.com/doc/ba17738243.html,t;

if(cur_volu.cur||u.cur<=0) continue;

//左子树

Heap

lson=Heap(u.cur1,u.val+ns[u.cur].a,u.vol+ns[u.cur].b,https://www.doczj.com/doc/ba17738243.html,t+1,u.val+ns[u.cur].a+dp[u.cur-1][k-1-u.c nt]);

pq.push(lson);

//右子树，一个小条件提前判断一下

if(u.cur-1>=https://www.doczj.com/doc/ba17738243.html,t){

Heap rson=Heap(u.cur-1,u.val,u.vol,https://www.doczj.com/doc/ba17738243.html,t,u.val+dp[u.cur-1][https://www.doczj.com/doc/ba17738243.html,t]);

pq.push(rson);

}

printf("%d %d\n",k,suma-res);

return 0;

}

屠龙宝镜

#include

#define N 1001 #define INF 1000000 #define left 1

#define Separator -1 using namespace std; char map[N][N];

int usedmap[N][N];

queue xque;

queue yque;

queue derectionque;

int layer=1;

void quepush(int y,int x,int derection){

xque.push(x);

yque.push(y);

derectionque.push(derection);

usedmap[y][x] = layer;

}

void quepop(int &y,int &x,int &derection){

x = xque.front();

y = yque.front();

derection = derectionque.front();

xque.pop();

yque.pop();

derectionque.pop();

}

int derecty[] = {-1, 0, 0, 1};

int derectx[] = { 0,-1, 1, 0};

int main(){

int m,n,i,j;

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

for(i=0;i

for(j=0;j

usedmap[i][j] = INF;

}

for(i=0;i

if(map[0][i]=='#') quepush(0,i,left);

}

if(!xque.empty()) quepush(N-1,N-1,Separator);

layer++;

while(!xque.empty()){

int _y, _x, derection;

quepop(_y, _x, derection);

if(derection==Separator){

if(!xque.empty()) quepush(N-1,N-1,Separator);

layer++;

}else{

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

if(d!=derection&&d!=(3-derection)){ //进入的一列或者一行不遍历

for(int x =_x+derectx[d],y=_y+derecty[d]; x>=0&&x=0&&y

if(map[y][x] == '#' && usedmap[y][x] == INF) quepush(y,x,3-d);

}

int ans = INF;

for(i=0;i

if(usedmap[n-1][i]

}

if(n==1) ans=0;

printf("%d", (ans!=INF)?ans:-1);

return 0;

}