没有样例

一维i为商品下标，二维为A商品的状态由题共有0,1,2和\(\leq3\)四种状态，三维为B商品的状态由题共有0,1,2，三种状态。

由于A商品满三件以上为六折，不满为原价，不能放在同一个转移方程里，所以得分类讨论。

先算A没满三件的，都是原价，再算A满三件以上的，直接按6折算。

对于B来说，当第三维为3的时候，将三维状态转移为0，并且权+0。

为了保证免费的一定是三件商品里最小的且满足最少花费的条件，需要将B商品价格从大到小排序。

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;

int N,A[1007],B[1007];
int dp[1007][4][3];			//一维是商品的下标，二维是A商品只有012 和大于等于3这几种状态 
							//三维是B商品只有012 012 012模3的三种状态 
typedef struct
{
	int A;
	int B;
}p;

p C[1007];

bool cmp(p A,p B){	//以B商品价格从大到小排序 
	if(A.B>B.B)
		return 1;
	else
		return 0;
}

int main()
{
	
	scanf("%d",&N);
	for(int i=1;i<=N;i++)
		scanf("%d",&C[i].A);
	for(int i=1;i<=N;i++)
		scanf("%d",&C[i].B);
	sort(C+1,C+N+1,cmp);
	
	memset(dp,127,sizeof(dp));
	
	dp[0][0][0]=0;			//要分两种情况，A不满三件和 A满三件  			dp[1][1][0]=min(dp[0][0][0]+A,dp[1][1][0]
																	//		dp[4][0][0]=min(dp[4][0][0],dp[3][0][2]+B*0)   dp[4][0][1]=min(dp[4][0][1],dp[3][0][0]+B) 
	
	for(int i=1;i<=N;i++)
		for(int j=0;j<3;j++)		//先算A拿不满三件 
			for(int k=0;k<=2;k++)
			{
				dp[i][j+1][k]=min(dp[i][j+1][k],dp[i-1][j][k]+C[i].A*10) ;
				dp[i][j][(k+1)%3]=min(dp[i][j][(k+1)%3],dp[i-1][j][k]+(k==2 ? 0:C[i].B*10));
				//printf("dp[%d][%d][%d]=%d \n",i,j+1,k,dp[i][j+1][k]);
			}
	int ans1=1000000000;
	for(int j=0;j<3;j++)
		for(int k=0;k<=2;k++)
			ans1=min(ans1,dp[N][j][k]);		//先得到A不拿满三件的最优解 
	
	memset(dp,127,sizeof(dp));
	dp[0][0][0]=0;
	
	for(int i=1;i<=N;i++)
		for(int j=0;j<4;j++)		//再算A拿满三件 
			for(int k=0;k<=2;k++)
			{
				dp[i][min(j+1,3)][k]=min(dp[i][min(j+1,3)][k],dp[i-1][j][k]+C[i].A*6);
				dp[i][j][(k+1)%3]=min(dp[i][j][(k+1)%3],dp[i-1][j][k]+(k==2 ? 0:C[i].B*10));
				//printf("dp[%d][%d][%d]=%d \n",i,min(j+1,3),k,dp[i][min(j+1,3)][k]);
			}
	int ans2=1000000000;
	for(int k=0;k<=2;k++)
		ans2=min(ans2,dp[N][3][k]);
	//printf("%d %d\n",ans1,ans2);
	int ans=min(ans1,ans2);
	ans/=10;
	printf("%d",ans);
			
 } 

因为只涉及到i和i-1之间的状态转移，可以用滚动数组将dp[1000][4][3]的空间优化为dp[2][4][3]

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;

int N,A[1007],B[1007];
int dp[2][4][3];			//一维是商品的下标，二维是A商品只有012 和大于等于3这几种状态 
							//三维是B商品只有012 012 012模3的三种状态 
typedef struct
{
	int A;
	int B;
}p;

p C[1007];

bool cmp(p A,p B){	//以B商品价格从大到小排序 
	if(A.B>B.B)
		return 1;
	else
		return 0;
}

int main()
{
	
	scanf("%d",&N);
	for(int i=1;i<=N;i++)
		scanf("%d",&C[i].A);
	for(int i=1;i<=N;i++)
		scanf("%d",&C[i].B);
	sort(C+1,C+N+1,cmp);

	
	memset(dp,127,sizeof(dp));
	
	dp[0][0][0]=0;			//要分两种情况，A不满三件和 A满三件  			dp[1][1][0]=min(dp[0][0][0]+A,dp[1][1][0]
																	//		dp[4][0][0]=min(dp[4][0][0],dp[3][0][2]+B*0)   dp[4][0][1]=min(dp[4][0][1],dp[3][0][0]+B) 
	
	for(int i=1;i<=N;i++)
	{
		for(int j=0;j<3;j++)		//先算A拿不满三件 
			for(int k=0;k<=2;k++)
			{
				dp[i&1][j+1][k]=min(dp[i&1][j+1][k],dp[(i+1)&1][j][k]+C[i].A*10) ;
				dp[i&1][j][(k+1)%3]=min(dp[i&1][j][(k+1)%3],dp[(i+1)&1][j][k]+(k==2 ? 0:C[i].B*10));
				//printf("dp[%d][%d][%d]=%d \n",i,j+1,k,dp[i][j+1][k]);
			}
		memset(dp[(i+1)&1],127,sizeof(dp[(i+1)&1]));	//(i+1)&1在上面已经用掉了 初始化就行 
	}
	int ans1=1000000000;
	for(int j=0;j<3;j++)
		for(int k=0;k<=2;k++)
			ans1=min(ans1,dp[N&1][j][k]);		//先得到A不拿满三件的最优解 
	
	memset(dp,127,sizeof(dp));
	dp[0][0][0]=0;
	
	for(int i=1;i<=N;i++)
	{
		for(int j=0;j<4;j++)		//再算A拿满三件 
			for(int k=0;k<=2;k++)
			{
				dp[i&1][min(j+1,3)][k]=min(dp[i&1][min(j+1,3)][k],dp[(i+1)&1][j][k]+C[i].A*6);
				dp[i&1][j][(k+1)%3]=min(dp[i&1][j][(k+1)%3],dp[(i+1)&1][j][k]+(k==2 ? 0:C[i].B*10));
				//printf("dp[%d][%d][%d]=%d \n",i,min(j+1,3),k,dp[i][min(j+1,3)][k]);
			}
		memset(dp[(i+1)&1],127,sizeof(dp[(i+1)&1]));
	}
	int ans2=1000000000;
	for(int k=0;k<=2;k++)
		ans2=min(ans2,dp[N&1][3][k]);
	//printf("%d %d\n",ans1,ans2);
	int ans=min(ans1,ans2);
	ans/=10;
	printf("%d",ans);
			
 }