赤裸裸的DP题,简单题。
/*
ID:bysen
LANG:C++
PROG:shopping
*/
#include<stdio.h>
using namespace std;int ticket_No[100][6];
int ticket_Num[100][6];
int ticket_Money[100];
//票的成员，成员的数量,优惠金额int hash[1000];
//编号映射
int price[5];
//商品价格
int getGood[5];
//商品的数量int ticketNum;
int goodNum;int min( int a,int b ){ return a<b?a:b; }void init()
{for( int i=0;i<1000;i++ ) hash[i]=-1;int n;goodNum=0;scanf( "%d",&ticketNum );for( int i=0;i<ticketNum;i++ ){scanf( "%d",&n );for( int j=0;j<n;j++ )scanf( "%d %d",&ticket_No[i][j],&ticket_Num[i][j] );//获取优惠券上的产品编号与产品数量 scanf( "%d",&ticket_Money[i] );}for( int i=0;i<1000;i++ )hash[i]=0x7FF;scanf( "%d",&goodNum );for( int i=0;i<goodNum;i++ ){int no,num,p;scanf( "%d %d %d",&no,&num,&p );hash[no]=i;getGood[i]=num;price[i]=p;}
}void DP()
{int a[5];int dp[6][6][6][6][6];for( a[0]=0;a[0]<=getGood[0];a[0]++ )for( a[1]=0;a[1]<=getGood[1];a[1]++ )for( a[2]=0;a[2]<=getGood[2];a[2]++ )for( a[3]=0;a[3]<=getGood[3];a[3]++ )for( a[4]=0;a[4]<=getGood[4];a[4]++ ){dp[a[0]][a[1]][a[2]][a[3]][a[4]]=a[0]*price[0]+a[1]*price[1]+a[2]*price[2]+a[3]*price[3]+a[4]*price[4];if( a[0]-1>=0 )dp[a[0]][a[1]][a[2]][a[3]][a[4]]=min( dp[a[0]-1][a[1]][a[2]][a[3]][a[4]]+price[0],dp[a[0]][a[1]][a[2]][a[3]][a[4]] );if( a[1]-1>=0 )dp[a[0]][a[1]][a[2]][a[3]][a[4]]=min( dp[a[0]][a[1]-1][a[2]][a[3]][a[4]]+price[1],dp[a[0]][a[1]][a[2]][a[3]][a[4]] );if( a[2]-1>=0 )dp[a[0]][a[1]][a[2]][a[3]][a[4]]=min( dp[a[0]][a[1]][a[2]-1][a[3]][a[4]]+price[2],dp[a[0]][a[1]][a[2]][a[3]][a[4]] );if( a[3]-1>=0 )dp[a[0]][a[1]][a[2]][a[3]][a[4]]=min( dp[a[0]][a[1]][a[2]][a[3]-1][a[4]]+price[3],dp[a[0]][a[1]][a[2]][a[3]][a[4]] );if( a[4]-1>=0 )dp[a[0]][a[1]][a[2]][a[3]][a[4]]=min( dp[a[0]][a[1]][a[2]][a[3]][a[4]-1]+price[4],dp[a[0]][a[1]][a[2]][a[3]][a[4]] ); for( int k=0;k<ticketNum;k++ ){bool flag=true;int b[5];for( int i=0;i<5;i++ )b[i]=a[i];for( int i=0;ticket_No[k][i]!=0;i++ )//遍历优惠券{if( hash[ticket_No[k][i]]>goodNum )flag=false;else if( b[hash[ticket_No[k][i]]]-ticket_Num[k][i]>=0 ){b[hash[ticket_No[k][i]]]-=ticket_Num[k][i];}elseflag=false;} if( flag==false )continue;dp[a[0]][a[1]][a[2]][a[3]][a[4]]=min( dp[b[0]][b[1]][b[2]][b[3]][b[4]]+ticket_Money[k],dp[a[0]][a[1]][a[2]][a[3]][a[4]] );}//printf( "[%d][%d][%d][%d][%d]=%d\n",a[0],a[1],a[2],a[3],a[4],dp[a[0]][a[1]][a[2]][a[3]][a[4]] );}printf( "%d\n",dp[getGood[0]][getGood[1]][getGood[2]][getGood[3]][getGood[4]] );
}int main()
{freopen( "shopping.in","r",stdin );freopen( "shopping.out","w",stdout );init();DP();return 0;
}