记录编号	50341	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	还是“金明的预算方案”	最终得分	100
用户昵称	小白	是否通过	通过
代码语言	C++	运行时间	0.951 s
提交时间	2012-11-19 03:12:41	内存使用	0.34 MiB

#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>

using namespace std;

int F[ 3200 ];
int S[ 3200 ];
int v[ 61 ];
int p[ 61 ];
int q[ 61 ];
int f[ 61 ][ 11 ];

int main()
{
	freopen("budgetb.in","r",stdin);
	freopen("budgetb.out","w",stdout);
	int N,m,s;
	while ( cin >> N >> m >> s ) {
		N /= 10;
		int M = 1;
		while ( cin >> v[ M ] >> p[ M ] >> q[ M ] ) ++ M;
		
		memset( f, 0, sizeof( f ) );
		for ( int i = 1 ; i <= m ; ++ i ) {
			if ( q[ i ] ) 
				f[ q[ i ] ][ ++ f[ q[ i ] ][ 0 ] ] = i;
			v[ i ] /= 10;
		}
		
		memset( F, 0, sizeof( F ) );
		for ( int i = 1 ; i <= m ; ++ i )
		if ( !q[ i ] )
			for ( int j = N ; j >= v[ i ] ; -- j ) {
				// 对于 i 的附件 进行 背包求解 
				memset( S, 0, sizeof( S ) ); 
				for ( int k = 1 ; k <= f[ i ][ 0 ] ; ++ k ) {
					int now = f[ i ][ k ];
					for ( int l = j-v[ i ] ; l >= v[ now ] ; -- l )
						if ( S[ l ] < S[ l-v[ now ] ] + v[ now ]*p[ now ] )
							S[ l ] = S[ l-v[ now ] ] + v[ now ]*p[ now ];
				}
				
				for ( int l = j-v[ i ] ; l >= 0 ; -- l )
					if ( F[ j ] < F[ j-v[ i ]-l ] + v[ i ]*p[ i ] + S[ l ] )
						F[ j ] = F[ j-v[ i ]-l ] + v[ i ]*p[ i ] + S[ l ];
			}	
		cout << F[ N ]*10 << endl;
	}
	return 0;
}