uvaoj 2911Maximum贪心+数学

给定了两个数学表达式（如下图），求出给定式子的最大值。xi是满足条件的实数，m，p，a，b都是给定的整数，其中 m $\le$ 2000, p $\le$ 12 , p是偶数。

刚开始没什么思路，后来想到p是偶数，那就可以让xi的绝对值尽可能的大，因为要满足题目给定的条件，所以先取一部分数让他们的和是右边的部分。当b小于0时，左边界的那个负数，要有a*b个数才能满足情况；当b大于等于0时，取右边界的正数，要有b个数才能满足情况。这样就剩下了一些数，设剩下数的个数是count，可以先取一个右边界的正数，这样就需要有a个左边界的负数，绝对值是最大的，这样每次取a+1个数，一直取下去，就会还剩count%（a+1）个数，这样，可以除去一个外都取左边界的数，剩下的一个一定可以在给定的范围内找到一个数使得整个式子成立。这样，每个xi取得要么是左边界，要么是右边界，不可能有更优的解了。

写的时候，因为剩下count%（a+1）个数的时候，我直接减一算的，就可能得到-1，最后特判了下就过了。

代码如下：

/*************************************************************************
 > File Name: 2911.cpp
 > Author: gwq
 > Mail: gwq5210@qq.com 
 > Created Time: 2014年10月13日 星期一 01时49分28秒
 ************************************************************************/

#include <cmath>
#include <ctime>
#include <cctype>
#include <climits>
#include <cstdio>
#include <cstdlib>
#include <cstring>

#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <sstream>
#include <iostream>
#include <algorithm>

#define INF (INT_MAX / 10)
#define SQR(x) ((x) * (x))
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repf(i, a, b) for (int i = (a); i <= (b); ++i)
#define repd(i, a, b) for (int i = (a); i >= (b); --i)
#define clr(arr, val) memset(arr, val, sizeof(arr))
#define pb push_back
#define sz(a) ((int)(a).size())
#define middle(x, y) ((x + y) >> 1)

using namespace std;
typedef set<int> si;
typedef vector<int> vi;
typedef map<int, int> mii;
typedef long long ll;

const double esp = 1e-5;

int main(int argc, char *argv[])
{
 long long m, p, a, b;

 while (scanf("%lld%lld%lld%lld", &m, &p, &a, &b) != EOF) {
  double ans = 0.0;
  double tmp = pow(a, p / 2.0);
  if (b < 0) {
   m += a * b;
   ans -= a * b / tmp;
  } else {
   m -= b;
   ans += b * tmp;
  }

  ans += m / (a + 1) * (tmp + a / tmp);
  //特判一下，WA惨了
  if (m % (a + 1) != 0) {
   ans += (m % (a + 1) - 1) / tmp + pow(m % (a + 1) - 1, p) / tmp;
  }
  printf("%.0f\n", ans);
 }

 return 0;
}