paulzrm's blog

发表于 分类于

本文迁移自洛谷原文。

这里是官方题解

考虑到在所有的排序操作之后，之前的所有操作都会没有用。

所以我们只需要找到最后的一个排序操作后处理即可。

对于翻转，我们只需要设定一个变量。

如果是正序，，反之，

如果翻转了，

如果交换了：

当 时

当 时

最后输出即可。

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<iostream>
#include<cstdio>
using namespace std;
bool rev;
int ope[1000005];
int x[1000005],y[1000005];
int arr[1000005];
int main(){
	int n,m,lst;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i)arr[i]=i;
	for(int i=1;i<=m;++i){
		scanf("%d",ope+i);
		if(ope[i]==3)scanf("%d%d",x+i,y+i);
	}
	for(lst=m;lst;--lst)if(ope[lst]==1 or ope[lst]==2)break;
	if(ope[lst]==2)rev=1;
	else rev=0;
	for(int i=lst+1;i<=m;++i){
		if(ope[i]==3){
			if(not rev)swap(arr[x[i]],arr[y[i]]);
			else swap(arr[n-x[i]+1],arr[n-y[i]+1]);
		}else rev=1-rev;
	}
	if(rev==0)for(int i=1;i<=n;++i)printf("%d ",arr[i]);
	else for(int i=n;i;--i)printf("%d ",arr[i]);
	return 0;
}

发表于 分类于

本文迁移自洛谷原文。

我们不难发现毒瘤们想让我们写状压dp，所以我们考虑如何不写状压dp。

由于这题的数据范围很小，所以我们可以考虑随机。

假设当前随机到的数为tmp，则分为3种情况：

1.将所有的点设置为”选择”（因为我们可能在一开始有一个不好的开头）

2.随机删除一条边

3.随机补回一条边

由于要使得最终结果最小，所以2的概率要大点

测试得到1为，2为，3为时可以过。

上代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include<bits/stdc++.h>
using namespace std;
const int mxn=15;
vector<short>g[mxn];
short n,m;
vector<pair<short,short> >edges,cur;
vector<pair<short,short> >erases,ans;
bool used[mxn];
inline bool go(){  //直接暴力判边双
	for(short i=0;i<cur.size();++i){
		memset(g,0,sizeof(g));
		for(short j=0;j<cur.size();++j)if(i!=j)g[cur[j].first].push_back(cur[j].second),g[cur[j].second].push_back(cur[j].first);
		memset(used,0,sizeof(used));
		queue<int>q;q.push(1);
		for(;q.size();){
			int p=q.front();q.pop();
			for(int j=0;j<g[p].size();++j){
				if(!used[g[p][j]]){
					used[g[p][j]]=1;
					q.push(g[p][j]);
				}
			}
		}
		for(short i=1;i<=n;++i)if(!used[i])return 0;
	}
	return 1;
}
inline void solve(){
	cin>>n>>m;
	for(short i=1,x,y;i<=m;++i){
		cin>>x>>y;
		edges.push_back({x,y});
		ans.push_back({x,y});
	}
	clock_t St=clock();
	cur=edges;
	for(;clock()-St<1900;){  //卡时间
		short rd=rand();
		if(rd%1024==0 or edges.size()==0){
			cur=edges;
			erases.clear();
			continue;
		}
		if(rd%4 or !erases.size()){
			short tmp=rand()%(cur.size());
			pair<short,short>pt=cur[tmp];
			cur.erase(cur.begin()+tmp);
			if(go()){
				if(cur.size()<ans.size())ans=cur;
			}else{
				cur.push_back(pt);
			}
		}else{
			short tmp=rand()%(erases.size());
			cur.push_back(erases[tmp]);
			erases.erase(erases.begin()+tmp);
		}
	}
	cout<<ans.size()<<'\n';
	for(short i=0;i<ans.size();++i)cout<<ans[i].first<<' '<<ans[i].second<<'\n';
}
int main(){
	srand(time(NULL));
	ios_base::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	short T=1;//cin>>T;
	for(;T--;)solve();
}

发表于 分类于

本文迁移自洛谷原文。

来个python题解

由于只是要求A是B的子串，而没有限制长度最短（如果限制的话就比这难得多了），所以我们可以贪心的让B为A+A的反串。

代码如下：

1
2
3
4
5
6
s=input()
print("zrmtcl"+s+s[::-1]+"lctmrz")

# s[::-1]表示s的反串

# 由于限制B长度远大于A的长度的2倍，所以我们可以加一些私货（雾

发表于 分类于

本文迁移自洛谷原文。

结论+dp

我们可以先观察样例。当 时，整个序列的最大值为8。在merge后的序列中8后面的数在原序列中一定跟在8后面。同理得，在7后面8前面的所有数都一定跟在7后面。

于是原序列被分成了很多小段。现在要做的事就是将这些小段重新组合，得到两个长度为 的原序列。由于你已经分好了，所以你不需要知道小段内的内容，只要知道它们的长度，然后01背包即可。

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include<bits/stdc++.h>
using namespace std;
const int mxn=4002;
vector<int>g[mxn];
int n,m;
int a[mxn],pos[mxn];
bool ban[mxn];
vector<int>v;
int dp[mxn][mxn];
inline void solve(){
	cin>>n;for(int i=1;i<=n*2;++i)pos[i]=0;//千万不能用memset！会TLE！
	for(int i=1;i<=n*2;++i)ban[i]=0;
	v.clear();
	for(int i=1;i<=n*2;++i)cin>>a[i],pos[a[i]]=i;
	for(int i=n*2;i;--i){              //分割
		int cnt=0;
		for(int j=pos[i];j<=n*2 and !ban[j];)++cnt,ban[j]=1,++j;
		if(cnt)v.push_back(cnt);
	}
	for(int i=0;i<=v.size();++i)for(int j=0;j<=n;++j)dp[i][j]=0;
	dp[0][0]=1;
	sort(v.begin(),v.end());
	for(int i=0;i<v.size();++i){       //背包
		for(int j=0;j<=n;++j){
			if(dp[i][j]==1){
				dp[i+1][j]=1;
				if(j+v[i]<=n){
					dp[i+1][j+v[i]]=1;
				}
			}
		}
	}
	if(dp[(int)(v.size())][n])cout<<"YES\n";
	else cout<<"NO\n";
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int T=1;cin>>T;
	for(;T--;)solve();
}

发表于 分类于

本文迁移自洛谷原文。

做为出题人来一发（

首先，我们可以想到，敌人有很多是重复的，所以每一个位置上只留一个敌人即可。

然后，我们可以贪心的想：走到一个位置以后，等着别人来送死。

如何求出这个位置？

将这棵树，以任意一个节点为根，遍历一遍。

然后我们需要截取出“有用”的一块。（定义“有用”的一块为会被至少一个人走过的路径）

于是，我们可以让自己的初始位置为根，遍历一边这棵老树。

从所有有用的点出发，往上遍历，途中所有的点都变成有用的点。

然后删掉所有没有用的点即可。

然后，在这棵新的树上，找到最长链。

这个“最优点”一定就是这条最长链的中点了。（它到所有的叶子的距离的最大值最小。）

然后二分答案即可。

对于每一个二分到的值，循环所有有人站着的点，判断它的mid被祖先与你的初始位置的mid辈祖先之间的距离是否。

这个距离也可以用LCA求出:deep[x]+deep[y]-deep[LCA(x,y)]*2

复杂度：

优化：对于最后一步，每一次二分只需要枚举3个点(自己，最长链的两端)即可。

并且将二分去掉，直接暴力即可。（删了那个预处理的）

复杂度：

贪心 证明

为什么这个贪心是正确的？

你要走的话，必定向着敌人走。而且是最远的，不然没有意义。

首先，我们可以选出两个敌人(和)，使得他们和自己组成一个三人组，并且x到y的最短路径经过你，且你们三个人之间互相到达的最小距离最大。

然后，假设你和的距离为,你和的距离为。

如果你走向x，杀死他后再返回杀死，那么你走到路程为

待着不动的话，结果为

当a,b均小于k:都为。√

当或小于(一个):化简为

走向：

不动：

于是这个可以特判（??

不，（详细见后文）

均大于：

走向：

不动： (这里出问题了？？？

不，其实没有

因为我们要走到的标准位置上，或者

证毕。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
#include<bits/stdc++.h>
#define uint unsigned int
using namespace std;
template<class T>
class myVector{
    private:
        T* data;
        int len;
        int size;
    public:
        myVector(){
            data=NULL;
            len=size=0;
        }
        void clear(){
            data=NULL;
            len=size=0;
		}
        myVector(int _len){
            data=new T[_len];
            len=_len;
            size=0;
        }
        T& operator[](int index){return data[index];}
        const myVector& push_back(const T tmp){
            if(size>=len){
                T* newData=new T[len*2+1];
                memcpy(newData,data,len*sizeof(T));
                delete []data;
                data=newData;
                len=2*len+1;
            }
            data[size++]=tmp;
            return *this;
        }
        int getSize(){return size;}
};

const uint mxn=4e5+5;
myVector<uint>g[mxn];
uint n,m,k,p[mxn],hv[mxn],son[mxn];
uint deg[mxn],par[mxn],deep[mxn];
myVector<uint>alive;
bool used[mxn];
bool ban[mxn];
void goup(register uint x){
	if(used[x] or ban[x])return;
	used[x]=1;
	for(register uint i=0;i<g[x].getSize();++i)if(deep[g[x][i]]<deep[x])goup(g[x][i]);
}
uint dfs(register uint x,uint pa,uint dep){
	if(ban[x])return 0;
	par[x]=pa,deep[x]=dep,son[x]=1;
	for(register uint i=0;i<g[x].getSize();++i)if(g[x][i]!=pa)son[x]+=dfs(g[x][i],x,dep+1);
	return son[x];
}
myVector<uint>needs;
const uint maxn=5000;
char buffer[maxn],*S,*T;
char Get_Char(){
    if(S==T){
        T=(S=buffer)+fread(buffer,1,maxn,stdin);
        if(S==T)return EOF;
    }
    return *S++;
}

uint read(){
    char c;
    uint re=0,f=0;
    for(c=Get_Char();c<'0' or c>'9';c=Get_Char())if(c=='-')f=1;
    for(;c>='0' and c<='9';)re=(re<<1)+(re<<3)+(c-'0'),c=Get_Char();
    if(f)return -re;
    return re;
}

void read(register uint&x){
    char c;
    uint re=0,f=0;
    for(c=Get_Char();c<'0' or c>'9';c=Get_Char())if(c=='-')f=1;
    for(;c>='0' and c<='9';)re=(re<<1)+(re<<3)+(c-'0'),c=Get_Char();
    if(f)x=-re;
    else x=re;
}
inline int lca(int a,int b){
	if(deep[a]>deep[b])swap(a,b);
	for(;deep[b]>deep[a];)b=par[b];
	for(;a!=b;)a=par[a],b=par[b];
	return a;
}
signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	read(n);
	for(register uint i=1,u,v;i<n;++i){
		read(u),read(v);
		g[u].push_back(v);
		g[v].push_back(u);
		++deg[u],++deg[v];
	}
	read(m);
	for(register uint i=1;i<=m;++i)read(p[i]),hv[p[i]]=1;
	read(k),read(p[m+1]);hv[p[m+1]]=1;
	dfs(1,1,1);
	myVector<uint>vhv;vhv.clear();
	for(register uint i=1;i<=n;++i)if(hv[i])vhv.push_back(i);
	uint Root=vhv[0];
	dfs(Root,Root,1);
	for(register uint i=0;i<vhv.getSize();++i)goup(vhv[i]);
	for(register uint i=1;i<=n;++i)if(!used[i])ban[i]=1;
	alive.clear();
	for(register uint i=1;i<=n;++i)if(!ban[i])alive.push_back(i);
	if(!alive.getSize()){
		cout<<1<<endl;
		return 0;
	}
	memset(par,0,sizeof(par));
	dfs(alive[0],alive[0],1);
	uint mx=0,wz=0;
	uint po1,po2;
	for(register uint i=1;i<=n;++i)if(!ban[i] and deep[i]>mx){
		mx=deep[i];
		wz=i;
	}
	po1=wz;
	dfs(wz,wz,1);
	mx=0,wz=0;
	for(register uint i=1;i<=n;++i)if(!ban[i] and deep[i]>mx){
		mx=deep[i];
		wz=i;
	}
	po2=wz;
	uint mypos=p[m+1];
	uint ln=deep[po2]-1;
	uint md=po2;
	for(register uint i=1;i<=ln/2;++i)md=par[md];
	dfs(md,md,1);Root=md;
	needs.push_back(po1);needs.push_back(po2);needs.push_back(p[m+1]);
	uint a=po1,b=po2,c=p[m+1];
	bool da=0,db=0;
	int lac=lca(a,c),lbc=lca(b,c);
	bool ha=0,hb=0;
	for(register uint ans=1;ans<=ln;++ans){
		if(!da and deep[c]+deep[a]-2*deep[lac]<=k)da=1;
		if(!db and deep[c]+deep[b]-2*deep[lbc]<=k)db=1;
		if(da and db){
			cout<<ans<<'\n';
			return 0;
		}
		if(a==lac or c==lac)ha=1;
		if(b==lbc or c==lbc)hb=1;
		if(a!=md)a=par[a];
		if(b!=md)b=par[b];
		if(c!=md)c=par[c];
		if(ha)lac=par[lac];
		if(hb)lbc=par[lbc];

	}
	return 0;
}

发表于 分类于

本文迁移自洛谷原文。

首先，我们可以先选择题目，再把剩下不要的让家长拿走。这一定是最优的。

然后就是个基础的背包。dp[i][j]表示考虑带第i个题目时，花费了j个时间的最大毒瘤值。
为了最后的计算，还要记录一下路径。

最后通过记录的路径求出选了那些题目，然后贪心的从大到小排序，选前k个*2即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<bits/stdc++.h>
using namespace std;
int dp[101][1001],par[101][1001],k;
int a[101],b[101],n,m;
int main(){
	cin>>n>>m>>k;
	for(int i=1;i<=n;++i)cin>>a[i]>>b[i];
	for(int i=1;i<=n;++i){
		for(int j=0;j<=m;++j){
			dp[i][j]=dp[i-1][j],par[i][j]=j;
			if(j>=b[i]){
				if(dp[i][j]<dp[i-1][j-b[i]]+a[i]){
					dp[i][j]=dp[i-1][j-b[i]]+a[i];
					par[i][j]=j-b[i];  //记录路径
				}
			}
		}
	}
	vector<int>v;v.clear();
	int mx=-1,wz,ans=0;
	for(int i=0;i<=m;++i){
		if(dp[n][i]>mx){
			mx=dp[n][i];
			wz=i;
		}
	}
	for(int i=n;i;--i){
		int T=par[i][wz];
		if(T==wz);
		else{
			v.push_back(a[i]);
			wz=T;
		}
	}
	sort(v.rbegin(),v.rend());
	if(!v.size()){  //一个特判
		cout<<0<<'\n';
		return 0;
	}
	if(v.size()==n)v.pop_back();
	for(int i=0;i<v.size();++i){
		if(i<k)ans+=v[i]*2;
		else ans+=v[i];
	}
	cout<<ans<<'\n';
}

发表于 分类于

本文迁移自洛谷原文。

这题线段树、珂朵莉树的题解都有了，我来个分块吧/cy

分块维护每一个块内的状况，如果遇到整块涂色则打上标记，可以将时间复杂度保持在

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<bits/stdc++.h>
#define ll long long
#define mp make_pair
using namespace std;
const int mxn=1e5+5;
ll n,m,sn,a[mxn],b[mxn],ta[444],sb[444],tb[444],ans,th,tl,tr;
int main(){
	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>m,sn=sqrt(n);
	for(int i=0;i<n;++i)a[i]=i+1;   //初始状况
	for(;m--;){
		int tmp,l,r;cin>>tmp>>l>>r,--l,--r;
		if(tmp==1){
			int x;cin>>x;
			for(int i=l;i<=r;){   //分块处理
				th=i/sn,tl=th*sn,tr=min(tl+sn,n);
				if(i==tl and r>=tr-1){
					if(ta[th])tb[th]+=abs(ta[th]-x),sb[th]+=abs(ta[th]-x)*(tr-tl);    //可以整体覆盖
					else for(int i2=tl;i2<tr;++i2)b[i2]+=abs(a[i2]-x),sb[th]+=abs(a[i2]-x);  //一个一个来
					ta[th]=x,i=tr;
				}else{
					if(ta[th]){
						for(int i2=tl;i2<tr;++i2)a[i2]=ta[th];
						ta[th]=0;
					}
					b[i]+=abs(a[i]-x),sb[th]+=abs(a[i]-x),a[i]=x,++i;
				}
			}
		}else{
			ans=0;
			for(int i=l;i<=r;){  //分块求和
				tl=i/sn*sn,tr=min(tl+sn,n),th=i/sn;
				if(i==tl and r>=tr-1)ans+=sb[th],i=tr;
				else ans+=tb[th]+b[i],++i;
			}
			cout<<ans<<endl;
		}
	}
	return 0;
}

发表于 分类于

本文迁移自洛谷原文。

没有python题解？我来水一发

直接暴力枚举有多少门得了两分，一个一个判断即可

1
2
3
4
5
6
7
8
9
10
n,k=map(int,input().split())
def check(x):
    tk=k-x*2
    tn=n-x
    return tn*3<=tk and tk<=tn*5 #注意是tn*3 因为剩下的科目至少3分
for i in range(0,n+1):    #python的循环是左闭右开
    if check(i):
        print(i)
        break

发表于 分类于

本文迁移自洛谷原文。

自己的题，怎么能不写题解呢？

考察点：构图

我们可以新建个点:

第个点表示这个数

对于所有的，将i与所有是的约数的平方数的平方根所对应的节点号连一条边，权值为这个平方根

这样就可以转换成一个图论问题了！

也就是说，对于这张图，选出最大数量的点，使得两两之间不能由权值大于的边相连。

我们很容易就可以发现， 在一个由权值大于所组成的联通快中，最多只能选择一个。

所以跑边dfs就可以了！

注意点1:

由于有个点和询问，所以裸的是过不了的

通过打表可以发现，有很大一部分询问的答案是相同的

最多只需要查找次即可。

所以只需要找到这个临界值就可以了

2.如何O()求出?

1
2
3
4
5
6
7
8
9
10
11
res=1;i=1
while i*i*i<=b[i]:
	cnt=0
	while b[i]%i==0:
		cnt=cnt+1
		b[i]=b[i]/i
	res=max(res,cnt)
last_b=b[i]
tmp=sqrt(b[i])
if tmp*tmp==b[i]:res=max(res,2)
return res

为什么这段代码是正确的？

假设

因为所有的 因数都已经被while除完了

所以一定为两个挺大的，互质的数

所以只要特判一下是否相等即可

std:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include<bits/stdc++.h>
#define mp make_pair
#define ll long long
using namespace std;
const int mxn=1000005;//real: 200000
int n,m;
int a[mxn],b[mxn],c[mxn];
vector<int>g[mxn];
int overban,t_o,mx;
bool use[mxn];
inline void dfs(int x){
	if(use[x])return;
	use[x]=1;
	if(x<=n)mx=max(mx,c[x]);
	for(int it=0;it<g[x].size();++it){
		int y=g[x][it];
		int ma=max(x,y);
		if(ma<=overban)continue;
		dfs(y);
	}
}
inline pair<int,int> solve(int xx){
	overban=xx;
	t_o=xx-n;
	int res=0,cnt=0;
	memset(use,0,sizeof(use));
	for(int i=1;i<=n;++i){
		if(!use[i]){
			mx=0;
			dfs(i);
			if(mx)++cnt;
			res+=mx;
		}
	}
	return mp(cnt,res);
}
pair<int,int>ans[mxn];
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i){
		scanf("%d",a+i);
		for(int x=2;x*x<=a[i];++x){
			if(a[i]%(x*x)==0){
				g[i].push_back(n+x);
				g[n+x].push_back(i);
			}
		}
	}
	for(int i=1;i<=n;++i){   //b[i]^(1/3) calc c[i]
		scanf("%d",b+i);
		int t=b[i],res=1;
		for(int x=2;x*x*x<=t;++x){
			int c=0;
			for(;t%x==0;t/=x)++c;
			res=max(res,c);
		}
		int t2=sqrt(t);
		if(t2*t2==t)res=max(res,2);
		else res=max(res,1);
		c[i]=res;
	}
	for(int i=1;i<=200000;++i){
	    if(ans[i-1].first==n){
	        ans[i]=ans[i-1];
	        continue;
	    }
	    ans[i]=solve(i+n);
	}
	for(int i=1;i<=m;++i){
		int x;scanf("%d",&x);
		printf("%d %d\n",ans[x].first,ans[x].second);
	}
	return 0;
}

发表于 分类于

本文迁移自洛谷原文。

在1:43时A掉了这一题，成功翻盘，rank34

题解：

贪心+dp

首先我们可以发现，如果一个城堡是可以被守卫的，那么，我们就会尽可能的让他往后被守卫。

为什么呢？

因为，如果在前面就守卫了，也许就会影响到后面的关卡过不去。而到了最后，如果你再不守卫的话，那么就没有机会了。但是如果到最后再守卫，造成的代价与之前一样，但是可以让他有更多的机会去进攻。

dp:

令dp[i][j]表示考虑到第i个城堡时，剩余了j个人时的最大成果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
inline void solve(){
	cin>>n>>m>>k;
	for(int i=1;i<=n;++i)cin>>a[i]>>b[i]>>c[i];  //读入
	checkbad();                       //特判-1
	for(int i=1;i<=m;++i){
		int u,v;
		cin>>u>>v;
		lst[v]=max(lst[v],u);             //找最后
	}
	for(int i=1;i<=n;++i){
		lst[i]=max(lst[i],i);
		v[lst[i]].push_back(i);
	}
	for(int i=1;i<=n;++i)sort(v[i].begin(),v[i].end(),cmp);  //贪心
	for(int i=1;i<=n;++i)for(int j=0;j<=5000;++j)dp[i][j]=-INf; //初始化
	dp[1][k]=0;
	for(int i=1;i<=n;++i){
		for(int j=a[i];j<=5000;++j){
			dp[i+1][j+b[i]]=max(dp[i+1][j+b[i]],dp[i][j]);  //不选
			int sum=0,cnt=0;
			for(int f:v[i]){  //贪心的选
				sum+=c[f];
				++cnt;
				if(j+b[i]-cnt>=0)dp[i+1][j+b[i]-cnt]=max(dp[i+1][j+b[i]-cnt],dp[i][j]+sum);
				else break;   //优化
			}
		}
	}

0%