CodeForces 28D Don't fear, DravDe is kind dp

为了让球队后，删除是合法的。也就是说，对于每一个车辆， l+r+c 一样，按l+r+c分类。
然后dp一下。
#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#include <math.h>

#include <set>

#include <vector>

#include <map>

using namespace std;

#define ll int

#define N 100005

struct node{

	int v,c,l,r;

	int num;

}car[N];

ll n;

vector<int>G[N], tmp;

set<int> myset;

set<int> ::iterator p;

map<int,int> mymap;

map<int,int> per;

map<int,int> sig;

int pos[N], endpos;

ll work(ll x){

	if(G[x].size()==0)return 0;

	mymap.clear();

	per.clear();

	sig.clear();

	mymap[0] = 0;

	per[0] = -1;

	sig[0] = -1;

	int ans = 0;

	endpos = -1;

/*	cout<<"---x:"<<x<<endl;

	for(int i = 0; i < G[x].size(); i++)cout<<G[x][i]<<" ";

	puts("---");/**/

	for(int i = 0; i < G[x].size(); i++) {

		node now = car[G[x][i]];

		if(mymap.find(now.l)==mymap.end())

			continue;

	//	cout<<"now: "<<G[x][i]<<endl;

		if(mymap.find(now.l+now.c)==mymap.end() || mymap[now.l+now.c]<mymap[now.l]+now.v) {

			mymap[now.l+now.c] = mymap[now.l]+now.v;

			sig[now.l+now.c] = G[x][i];

			per[G[x][i]] = sig[now.l];

		}

		if(now.r==0 && ans<mymap[now.l+now.c])ans = mymap[now.l+now.c], endpos = G[x][i];

	}

	return ans;

}

int main(){

	ll i,j,u,v;

	while(cin>>n){

		for(i = 1; i <= n; i++) G[i].clear();

		myset.clear();

		mymap.clear();

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

			scanf("%d%d%d%d",&car[i].v,&car[i].c,&car[i].l,&car[i].r), car[i].num = i;

		for(i = 1; i <= n; i++) {

			myset.insert(car[i].c+car[i].l+car[i].r);

		}

		i = 1;

		for(p = myset.begin(); p!=myset.end(); p++, i++)

			mymap[*p] = i, pos[i] = *p;

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

			G[mymap[car[i].c+car[i].l+car[i].r]].push_back(i);

		int ans = 0;

		for(i = 1; i <= n; i++) {

			int now = work(i);

			if(now>ans) {

				ans = now;

				tmp.clear();

				u = endpos;

				while(u!=-1) {

					tmp.push_back(u);

					u = per[u];

				}

			}

		}

		cout<<tmp.size()<<endl;

		for(i = tmp.size()-1; i>=0; i--)

			printf("%d%c",tmp[i],i?' ':'\n');

	}

	return 0;

}