2015 计蒜客初赛题解之工作区的颜值选择

标签（空格分隔）： ACM

简单数据暴力代码

#include <iostream>
#include <cstdio>
using namespace std;
const int Maxn = 2, Maxm = 3;
int C[Maxn][Maxm], U[Maxn][Maxm], W[Maxn][Maxm];
int n, m, k;
inline int abs(int x) {
return x < 0 ? -x : x;
}
inline int cost(int c, int i, int j) {
return (abs(c + i + j + 2) ^ U[i][j]) * W[i][j];
}
int dirx[] = {-1, 0, 1, 0};
int diry[] = {0, -1, 0, 1};
int optimize(int x, int y) {
if (y >= m) return 0;
if (x >= n) return optimize(x ^ 1, y + 1);
int best = -1;
for (int i = -k; i <= k; ++i) {
int tmp = cost(i,x, y);
for (int l = 0; l < 4; ++l) {
int nx = dirx[l] + x;
int ny = diry[l] + y;
if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            tmp += abs(i + C[nx][ny]);
        }
if (best == -1 || tmp < best) best = tmp;
    }
return best + optimize(x ^ 1, y + 1);
}
int solve(int x, int y) {
if (y >= m) return optimize(1, 0);
if (x >= n) return solve(x ^ 1, y + 1);
int ans = -1;
for (int i = -k; i <= k; ++i) {
        C[x][y] = i;
if (ans == -1) ans = solve(x ^ 1, y + 1) + cost(i, x, y);
else ans = min(ans, solve(x ^ 1, y + 1) + cost(i, x, y));
    }
return ans;
}
int main(){
scanf("%d %d %d", &n, &m, &k);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
scanf("%d", &U[i][j]);
        }
    }
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
scanf("%d", &W[i][j]);
        }
    }
printf("%d\n", solve(0, 0));
return 0;
}

中等数据动态规划代码（题目范围出错 n可以等于1）

#include <iostream>
#include <cstdio>
using namespace std;
const int Maxn = 2, Maxm = 33, Maxk=33, INF = 0x7FFFFFFF;
int U[Maxn][Maxm], W[Maxn][Maxm];
int n, m, k;
inline int abs(int x) {
return x < 0 ? -x : x;
}
inline int cost(int c, int i, int j) {
return (abs(c + i + j + 2) ^ U[i][j]) * W[i][j];
}
inline int ID(int x) {
return x + Maxk;
}
int dp[Maxm][Maxk << 1][Maxk << 1];
int neg_decision[Maxm][Maxk << 1][Maxk << 1];
int pos_decision[Maxm][Maxk << 1][Maxk << 1];

int solve() {
for (int i = -k; i <= k; ++i) {
for (int j = -k; j <= k; ++j) {
            dp[0][ID(i)][ID(j)] = cost(i, 0, 0) + cost(j, 1, 0) + abs(i + j);
        }

int neg = -k;
int pos = k;
for (int j = -k; j <= k; ++j) {
if (dp[0][ID(i)][ID(j)] - j < dp[0][ID(i)][ID(neg)] - neg)
                neg_decision[0][ID(i)][ID(j)] = j;
else neg_decision[0][ID(i)][ID(j)] = neg;

if (dp[0][ID(i)][ID(-j)] - j < dp[0][ID(i)][ID(pos)] + pos)
                pos_decision[0][ID(i)][ID(-j)] = -j;
else pos_decision[0][ID(i)][ID(-j)] = pos;

            neg = neg_decision[0][ID(i)][ID(j)];
pos = pos_decision[0][ID(i)][ID(-j)];
        }
    }

for (int t = 1; t < m; ++t) {
for (int i = -k; i <= k; ++i) {
for (int j = -k; j <= k; ++j){
int& tmp = dp[t][ID(i)][ID(j)]; 
                tmp = INF;
for (int l = -k; l <= k; ++l) {
int _neg = neg_decision[t - 1][ID(l)][ID(-j)];
int _pos = pos_decision[t - 1][ID(l)][ID(-j)];
                    tmp = min(dp[t - 1][ID(l)][ID(_neg)] - _neg - j  + abs(l + i), tmp);
                    tmp = min(dp[t - 1][ID(l)][ID(_pos)] + _pos + j  + abs(l + i), tmp);
                }
                tmp += abs(i + j) + cost(i, 0, t) + cost(j, 1, t);
            }
int neg = -k;
int pos = k;
for (int j = -k; j <= k; ++j){
if (dp[t][ID(i)][ID(j)] - j < dp[t][ID(i)][ID(neg)] - neg)
                    neg_decision[t][ID(i)][ID(j)] = j;
else neg_decision[t][ID(i)][ID(j)] = neg;
if (dp[t][ID(i)][ID(-j)] - j < dp[t][ID(i)][ID(pos)] + pos)
                    pos_decision[t][ID(i)][ID(-j)] = -j;
else pos_decision[t][ID(i)][ID(-j)] = pos;

                neg = neg_decision[t][ID(i)][ID(j)];
pos = pos_decision[t][ID(i)][ID(-j)];
            }
        }
    }
int ans = INF;
for (int i = -k; i <= k; ++i)
for (int j = -k; j <= k; ++j)
            ans = min(ans, dp[m - 1][ID(i)][ID(j)]);
return ans;
}
int dp1[Maxm][Maxk << 1];
int solve_n_1() {
for (int i = -k; i <= k; ++i)
        dp1[0][ID(i)] = cost(i, 0, 0);
for (int t = 1; t < m; ++t) {
for (int i = -k; i <= k; ++i) {
            dp1[t][ID(i)] = INF;
for (int j = -k; j <= k; ++j) {
                dp1[t][ID(i)] = min(dp1[t][ID(i)], dp1[t - 1][ID(j)] + abs(i + j) + cost(i, 0, t));
            }
        }
    }
int ans = INF;
for (int i = -k; i <= k; ++i)
        ans = min(ans, dp1[m - 1][ID(i)]);
return ans;
}
int main(){
    scanf("%d %d %d", &n, &m, &k);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
            scanf("%d", &U[i][j]);
        }
    }
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
            scanf("%d", &W[i][j]);
        }
    }
if (n == 1) printf("%d\n", solve_n_1());
else printf("%d\n", solve());
return 0;
}

困难数据网络流代码

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int MAXN = 100000, INF = (1 << 30) - 1;
const int Maxn = 33, Maxm = 33, Maxk=33;
int U[Maxn][Maxm], W[Maxn][Maxm];
int n, m, k;
inline int abs(int x) {
return x < 0 ? -x : x;
}
inline int cost(int c, int i, int j) {
return (abs(c + i + j + 2) ^ U[i][j]) * W[i][j];
}
struct Edge {
int to, f, next;
    Edge(){}
    Edge(int to, int f, int next): to(to), f(f), next(next){}
}edge[MAXN * 4];
int box[MAXN], size;
void add(int from, int to, int f){
    edge[size] = Edge(to, f, box[from]);
    box[from] = size++;
}

int deep[MAXN],depnum[MAXN];// depnum记录各个距离的个数
bool isEnd;
int s,t,N;
void bfs()//反向分层
{
memset(deep,-1,sizeof(deep));
memset(depnum,0,sizeof(depnum));
    deep[t]=0;
    depnum[0]++;
int que[MAXN],in=0,out=0;
    que[in++]=t;
while(in>out)
    {
int x=que[out++];
for(int i=box[x];i!=-1;i=edge[i].next)
        {
int x1=edge[i].to;
if(edge[i^1].f==0||deep[x1]!=-1)continue;
            que[in++]=x1;
            deep[x1]=deep[x]+1;
            depnum[deep[x1]]++;
        }
    }
if(deep[s]==-1) isEnd=true;
else isEnd=false;
}
int dfs(int x,int flow)
{
if(x==t)return flow; 
if(isEnd||flow==0)return 0;
int tmp=0;
int min1=deep[x]+1;
for(int i=box[x];i!=-1;i=edge[i].next)
    {
int x1=edge[i].to;      if(edge[i].f==0||deep[x1]==N||deep[x1]==-1)continue;
if(deep[x1]==deep[x]-1)//如果有有效路径则更新下一结点
        {
int tmp1=dfs(x1,min(edge[i].f,flow-tmp));
            edge[i].f-=tmp1;
            edge[i^1].f+=tmp1;
        tmp+=tmp1;  
        }
if(edge[i].f)min1=min(min1,deep[x1]+1);
    }  
    depnum[min1]++;
    depnum[deep[x]]--;
if(depnum[deep[x]]==0)isEnd=true;
    deep[x]=min1;
return tmp;
}
int sap()
{
//N=n+2;
//s=n,t=n+1;
int ans=0;
    bfs();
while(deep[s]<N&&!isEnd)
    {
        ans+=dfs(s,INF);
    }
return ans;
}

int solve() {
memset(box, -1, sizeof(box)); size = 0;
    s = 0;
    t = (2 * k + 2) * n * m + 1;
int id = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
int first = id * (2 * k + 2) + 1;
int last = first + 2 * k + 1;
for (int l = first; l < last; ++l) {
                add(l, l + 1, cost(-k + l - first, i, j));
                add(l + 1, l, cost(-k + l - first, i, j));
            }
if ((i + j) & 1) swap(first, last);
            add(s, first, INF);
            add(first, s, 0);
            add(last, t, INF);
            add(t, last, 0);  
            id++;
        }
    }

for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
int cur = (i * m + j) * (2 * k + 2) + 1;
if (j) {
int left = (i * m + j - 1) * (2 * k + 2) + 1;
for (int l = 0; l < 2 * k + 2; ++l) {
                    add (left + 2 * k + 1 - l, cur + l, 1);
                    add (cur + l, left + 2 * k + 1 - l, 1);
                }

            }
if (i) {
int up = ((i - 1) * m + j) * (2 * k + 2) + 1;
for (int l = 0; l < 2 * k + 2; ++l) {
                    add (up + 2 * k + 1 - l, cur + l, 1);
                    add (cur + l, up + 2 * k + 1 - l, 1);
                }
            }
        }
    }
    N = t + 1;

return sap();
}

int main(){
scanf("%d %d %d", &n, &m, &k);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
scanf("%d", &U[i][j]);
        }
    }
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
scanf("%d", &W[i][j]);
        }
    }
printf("%d\n", solve());
return 0;
}

秒客网

计蒜客2015 初赛题解及代码

2015 计蒜客初赛题解之工作区的颜值选择

相关文章