蒟蒻dp爆零,程序内层循环进不去
查看原帖
蒟蒻dp爆零,程序内层循环进不去
548794
丁焌永楼主2023/7/23 21:53
#include<iostream>
using namespace std;
int dp[351][41][41][41],c[5],p[351],n,m;
int _max(int i,int j1,int j2,int j3,int j4)
{
	int ans=0;
	if(j1>=1)ans=dp[i-1][j1-1][j2][j3];
	if(j2>=1&&i>=3)ans=max(ans,dp[i-2][j1][j2-1][j3]);
	if(j3>=1&&i>=4)ans=max(ans,dp[i-3][j1][j2][j3-1]);
	if(j4>=1&&i>=5)ans=max(ans,dp[i-4][j1][j2][j3]);
	
//	cout<<"*****\n";
	return ans;
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;++i)
		cin>>p[i];
	for(int i=1;i<=m;++i)
	{
		int op;
		cin>>op;
		c[op]++;
	}
	int i,j1,j2,j3;
	dp[1][0][0][0]=p[1];
	for(i=2;i<=n;++i)
		for(j1=0;j1<=c[1];++j1)
			if(i-1-j1>=0)
				for(j2=0;j2<=c[2];++j2)
					if(i-1-j1-j2*2>=0)
						for(j3=0;j3<=c[3];++j3);
						{
							int j4=i-1-j1-2*j2-3*j3;
							if(j4>=0&&j4<=c[4]*4&&j4%4==0)
								dp[i][j1][j2][j3]=_max(i,j1,j2,j3,j4/4)+p[i];
						}
/*	for(int i=1;i<=n;++i)
	{
		for(int j1=0;j1<=c[1];++j1)
		{
			for(int j2=0;j2<=c[2];++j2)
			{
				for(int j3=0;j3<=c[3];++j3)
					cout<<dp[i][j1][j2][j3]<<' ';
				cout<<endl;
			}
			cout<<endl;
		}
		cout<<endl;
	}*/
	cout<<dp[n][c[1]][c[2]][c[3]];
}
/*
9 5
6 10 14 2 8 8 18 5 17
1 3 1 2 1
*/
2023/7/23 21:53
加载中...