简单DP求助!!!
查看原帖
简单DP求助!!!
636936
tyccyt楼主2024/11/8 20:51

样例过了,但是WA on #2

#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define fi first
#define se second
#define ll long long
const int N=1e6+5;
int n,m,cnt=0,now=0;
priority_queue<int>t[4];
struct node
{
	ll op,a,b,c;
}a[N];
ll f[N][11];
inline int get(int id){return id%10;}
inline ll getm(int i){return max(a[i].a,max(a[i].b,a[i].c));}
inline ll gets(int i){return a[i].a+a[i].b+a[i].c;}
inline void solve()
{
	for(int i=now+1;i<=cnt;i++)
	{
		for(int k=0;k<=9;k++)f[i][k]=max(f[i-1][k],f[i][k]);
		for(int k=0;k<=9;k++)
		{
			if(a[i].op==1&&k==9||
			  (a[i].op==2&&(k==9||k==8))||
			  (a[i].op==3&&(k==7||k==8||k==9)))
			  f[i][get(k+a[i].op)]=max(f[i][get(k+a[i].op)],f[now][k]+gets(i)+getm(i));
			else f[i][get(k+a[i].op)]=max(f[i][get(k+a[i].op)],f[now][k]+gets(i));
		}
	}
	now=cnt;
}
int main()
{
	cin>>n;
	for(int i=1,mx11,mx12,mx13,mx2,mx3;i<=n;i++)
	{
		mx11=0,mx12=0,mx13=0,mx2=0,mx3=0;
		cin>>m;
		for(int j=1,c,d;j<=m;j++)
		{
			cin>>c>>d;
			t[c].push(d);
		}
		if(!t[1].empty())mx11=t[1].top();
		if(!t[1].empty())t[1].pop();
		if(!t[1].empty())mx12=t[1].top();
		if(!t[1].empty())t[1].pop();
		if(!t[1].empty())mx13=t[1].top();
		if(!t[2].empty())mx2=t[2].top();
		if(!t[3].empty())mx3=t[3].top();
		
		if(mx11&&mx12&&mx13)a[++cnt]=(node){3,mx11,mx12,mx13};
		if(mx11&&mx12)a[++cnt]=(node){2,mx11,mx12,0};
		if(mx12&&mx13)a[++cnt]=(node){2,mx12,mx13,0};
		if(mx11)a[++cnt]=(node){1,mx11,0,0};
		if(mx12)a[++cnt]=(node){1,mx12,0,0};
		if(mx13)a[++cnt]=(node){1,mx13,0,0};
		
		if(mx11&&mx2)a[++cnt]=(node){2,mx11,mx2,0};
		if(mx3)a[++cnt]=(node){1,mx3,0,0};
		if(mx2)a[++cnt]=(node){1,mx2,0,0};
		
		solve();
		
		while(!t[1].empty())t[1].pop();
		while(!t[2].empty())t[2].pop();
		while(!t[3].empty())t[3].pop();
	}
	ll mx=0;
	for(int j=0;j<=9;j++) mx=max(mx,f[cnt][j]);
	cout<<mx;
	return 0;
}
2024/11/8 20:51
加载中...