HDU 2082 단어 찾기 (가방)

링크:http://acm.hdu.edu.cn/showproblem.php?pid=2082
제목:
단어 마다 개 수 를 알려 줄 게!
그리고 가치: A 는 1. B 는 2... Z 는 26.
단어 가 서로 조 합 된 후 총 가치 가 50 보다 적은 단 어 는 몇 개 있 습 니까?
배낭
#include<iostream>  
#include<cstring>  
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<queue>
#include<map>
#include<stack>
#include<algorithm>
using namespace std;

int a[30];
int dp[30][51];
int main()
{
//	freopen("D://input.txt", "r", stdin);
//	freopen("D://output.txt", "w", stdout);
	int T;
	scanf("%d", &T);
	while (T--)
	{
		memset(dp, 0, sizeof(dp));
		int i, j, k;
		for (i = 1; i <= 26; i++)
			scanf("%d", &a[i]);
		for (i = 0; i <= 26; i++)
			dp[i][0] = 1;
		/*
		     ,     i            ,  dp             ,     
		*/
		for (i = 1; i <= 26; i++)//      
		{
			for (j = 0; j <= 50; j++)//    
			{
				dp[i][j] = dp[i - 1][j];//            
				for (k = 1; k <= a[i]; k++)//        
				{
					if (j >= k*i)//k*i k            ,  dp[i][j]    dp[i - 1][j - k*i]      
						dp[i][j] += dp[i - 1][j - k*i];//dp[i - 1][j - k*i]     i-1      ,  j - k*i      ,    
					else break;
				}
			}
		}
		int ans = 0;
		for (i = 1; i <= 50; i++)
			ans += dp[26][i];//   1 50        ,      26,           
		printf("%d
", ans); } // printf(".6lf
",(double)clock()/CLOCKS_PER_SEC); return 0; }

좋은 웹페이지 즐겨찾기