USACO 2016 January Contest, Gold解题报告

1.Angry Cows

http://www.usaco.org/index.php?page=viewproblem2&cpid=597

dp题+vector数组运用

将从左向右与从右向左扫描结合。先从左到右DP，确定每个干草捆向右爆炸的最小半径，再从右到左，确定每个干草捆向左爆炸的最小半径。通过扫描每个干草捆，用这两个数字来确定我们应该设置初始引爆点的最佳位置。

#include <cstdio>

#include <algorithm>

#include <vector>

using namespace std;

#define INF 2000000000

int main()

{

      //freopen("angry.in", "r", stdin);

      //freopen("angry.out", "w", stdout);

      int n;

      scanf("%d",&n);

      vector<int> a(n);

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

    {

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

        a[i]*=;

      }

      sort(a.begin(), a.end());

      a.resize(unique(a.begin(),a.end())-a.begin());

      vector<int> DP[];

      for(int it=;it<;it++)

    {

        int l=;

        DP[it].resize(n,INF);

        DP[it][]=-;

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

        {

              while(l+<i&&abs(a[i]-a[l+])>DP[it][l+]+)

            {

                l++;

              }

              DP[it][i]=min(abs(a[i]-a[l]),DP[it][l+]+);

        }

        reverse(a.begin(),a.end());

    }

      reverse(DP[].begin(),DP[].end());

      int i=,j=n-,res=INF;

     while(i<j)

    {

        res=min(res,max((a[j]-a[i])/,+max(DP[][i],DP[][j])));

        if(DP[][i+]<DP[][j-])

              i++;

        else

              j--;

      }

      printf("%d.%d\n",res/,(res%?:));

      return ;

}

2.Radio Contact

这个问题实际上是一个隐藏的动态时间扭曲问题，其中误差函数是FJ和Bessie之间的平方距离。

因此，可以通过动态编程解决问题。对于Farmer John和Bessie的每个可能的位置，我们可以通过尝试向前迈出FJ，向前走Bessie，向前移动他们来计算他们达到最终位置所需的最小能量。

#include <vector>

#include <cstring>

#include <cstdio>

#include <map>

#include <iostream>

using namespace std;

#define INF 0x7FFFFFFFFFFFFFFFLL

long long memo[][];

vector<pair<long long, long long> > F;

vector<pair<long long, long long> > B;

long long solve(int fi, int bi) {

  /* The energy cost of the radio for this timestep. */

  long long base = (F[fi].first - B[bi].first) * (F[fi].first - B[bi].first) +

             (F[fi].second - B[bi].second) * (F[fi].second - B[bi].second);

  if (fi +  == F.size() && bi +  == B.size()) {

    return base;

  }

  long long& ref = memo[fi][bi];

  if (ref != -) return ref;

  /* Don't include the cost of the first timestep. */

  if (fi ==  && bi == ) base = ;

  ref = INF;

  if (fi +  < F.size()) {

    /* Step FJ forward. */

    ref = min(ref, base + solve(fi + , bi));

  }

  if (bi +  < B.size()) {

    /* Step Bessie forward. */

    ref = min(ref, base + solve(fi, bi + ));

  }

  if (fi +  < F.size() && bi +  < B.size()) {

    /* Step both forward. */

    ref = min(ref, base + solve(fi + , bi + ));

  }

  return ref;

}

int main() {

  //freopen("radio.in", "r", stdin);

  //freopen("radio.out", "w", stdout);

  map<char, int> dx, dy;

  dx['E'] = ; dx['W'] = -;

  dy['N'] = ; dy['S'] = -;

  int N, M;

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

  int fx, fy, bx, by;

  scanf("%d%d%d%d",&fx,&fy,&bx,&by);

  string SF, SB;

  cin >> SF >> SB;

  /* Compute FJ's path. */

  F.push_back(make_pair(fx, fy));

  for (int i = ; i < SF.size(); i++) {

    fx += dx[SF[i]];

    fy += dy[SF[i]];

    F.push_back(make_pair(fx, fy));

  }

  /* Compute Bessie's path. */

  B.push_back(make_pair(bx, by));

  for (int i = ; i < SB.size(); i++) {

    bx += dx[SB[i]];

    by += dy[SB[i]];

    B.push_back(make_pair(bx, by));

  }

  memset(memo, -, sizeof(memo));

  cout << solve(, ) << endl;

  return ;

}

巴特西

USACO 2016 January Contest, Gold解题报告

1.Angry Cows

2.Radio Contact

最新文章

热门文章