ZOJ 3905 Cake

Cake

Time Limit: 4 Seconds       Memory Limit: 65536 KB

Alice and Bob like eating cake very much. One day, Alice and Bob went to a bakery and bought many cakes.

Now we know that they have bought n

Alice and Bob do n

Now Alice want to know the maximum sum of the value that she can get.

Input

The first line is an integer T

For each test case, the first line is an integer n (1<=n<=800). Note that n

In following n lines, each line contains two integers a[i] and b[i], where a[i] is the value of i^th cake that Alice evaluates, and b[i] is the value of i^th cake that Bob evaluates. (1<=a[i], b[i]<=1000000)

Note that a[1], a[2]..., a[n] are n distinct integers and b[1], b[2]..., b[n] are n

Output

For each test case, you need to output the maximum sum of the value that Alice can get in a line.

Sample Input

1 6 1 6 7 10 6 11 12 18 15 5 2 14

Sample Output

28

先按b从大到小排序，然后像做背包一样搞就好了

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1005;
int T,n,m,f[maxn][maxn];

struct point
{
  int a,b;
  void read(){scanf("%d%d",&a,&b);}
  bool operator<(const point&f) const
  {
    return b>f.b;
  }
}u[maxn];

int main()
{
  scanf("%d",&T);
  while (T--)
  {
    memset(f,0,sizeof(f));
    scanf("%d",&n);
    for (int i=1;i<=n;i++) u[i].read();
    sort(u+1,u+n+1);
    for (int i=1;i<=n;i++)
    {
      f[i][0]=0;
      for (int j=1;j+j<=i;j++)
      {
        f[i][j]=max(f[i-1][j],f[i-1][j-1]+u[i].a);
      }
    }
    printf("%d\n",f[n][n/2]);
  }
  return 0;
}