題意:覺得學長寫的很好,借鑒了:點擊打開鏈接
#include#include #include #include using namespace std; const int INF = 0x3f3f3f3f; const int MAXN = 1010; struct node{ int x,y; bool operator <(const node &a)const { if (x != a.x) return x > a.x; return y < a.y; } }arr[MAXN]; int n; int f[MAXN][MAXN/2]; int cost[MAXN][MAXN/2]; char name[10]; int main(){ int t; scanf("%d",&t); while (t--){ scanf("%d",&n); scanf("%s",name); int sum = 0; for (int i = 1; i <= n; i++){ scanf("%d%d",&arr[i].x,&arr[i].y); sum += arr[i].x; } sort(arr+1,arr+1+n); memset(f,0,sizeof(f)); memset(cost,0,sizeof(cost)); int cur = 0; for (int i = (name[0]=='P'?2:1); i <= n; i++){ ++cur; for (int j = 1; j <= (cur+1)/2; j++){ int &ans = f[i][j] = f[i-1][j]; cost[i][j] = cost[i-1][j]; if (j == 1 || f[i-1][j-1]){ int tmp = f[i-1][j-1] + arr[i].y; if (tmp > ans){ ans =tmp; cost[i][j] = cost[i-1][j-1] + arr[i].x; } else if (tmp == ans) cost[i][j] = min(cost[i][j],cost[i-1][j-1]+arr[i].x); } } } printf("%d %d\n",sum-cost[n][(cur+1)/2],f[n][(cur+1)/2]); } return 0; }