首页 > ACM题库 > HDU-杭电 > hdu 2697 WOJ-动态规划-[解题报告]C++
2014
02-13

hdu 2697 WOJ-动态规划-[解题报告]C++

WOJ

问题描述 :

Alex likes solving problems on WOJ (http://acm.whu.edu.cn/oak). As we all know, a beautiful balloon will appears when a
problem is solved. Alex loves balloons, especially when they’re in a consecutive column, from which he can get a sense of
accomplishment.

Problems on WOJ have a variety of difficulties. Hard problems cost more time, while easy ones may be "killed in 1
second". Now we know that WOJ has N problems, numbered from 1 to N. Alex calls the solved problems in one
consecutive column as a "successful string". The length of a successful string is the number of problems it contains. Also
he defines the value of a successful string as the square of the string’s length. Alex hopes to solve a certain number of
problems in M time, so he can get some successful strings, now he wants to maximize the sum of all the strings’ value.

输入:

The input consists of multiple test cases. The first line of input contains an integer T, which is the number of test cases.

The input consists of several test cases. Each test case starts with a line containing two integers N and M.
Each of the following N lines contains a single integer Mi indicating the time cost on solving the i-th problem.
(1<=N, M<=100)

[Technical Specification]
T is an integer, and T <= 15;
N and M are integers, 1 <= N, M <= 100.
Mi are integers and, 0 <= Mi <= 100

输出:

The input consists of multiple test cases. The first line of input contains an integer T, which is the number of test cases.

The input consists of several test cases. Each test case starts with a line containing two integers N and M.
Each of the following N lines contains a single integer Mi indicating the time cost on solving the i-th problem.
(1<=N, M<=100)

[Technical Specification]
T is an integer, and T <= 15;
N and M are integers, 1 <= N, M <= 100.
Mi are integers and, 0 <= Mi <= 100

样例输入:

1 
10 9 
6 
1
3 
1 
5 
3 
2 
5 
5 
5

样例输出:

10

dp[i][j]:从前i个中挑出某些且cost不超过j的最大val。

dp[i][j]:应该有1到i-1的dp[k][j-?]来更新!!

/*
 DP
 dp[i][j]:从前i个中挑出某些且cost不超过j的最大val。
 */
 #include<stdio.h>
 #include<string.h>
 #include<stdlib.h>
 #include<algorithm>
 #include<iostream>
 #include<queue>
 #include<map>
 #include<stack>
 #include<set>
 #include<math.h>
 using namespace std;
 typedef long long int64;
 //typedef __int64 int64;
 typedef pair<int64,int64> PII;
 #define MP(a,b) make_pair((a),(b)) 
 const int maxn = 105;
 const int inf = 0x7fffffff;
 const double pi=acos(-1.0);
 const double eps = 1e-8;
 int dp[ maxn ][ maxn ];
 int a[ maxn ];
 int main(){
     int T;
     scanf("%d",&T);
     while( T-- ){
         int n,sum;
         scanf("%d%d",&n,&sum);
         int MinCost = inf;
         for( int i=1;i<=n;i++ ){
             scanf("%d",&a[i]);
             if( a[i]<MinCost ) MinCost = a[i];
         }
         if( MinCost>sum ){
             printf("0\n");
             continue;
         }
         if( MinCost==sum ){
             puts("1");
             continue;
         }
         int ans = 0;
         memset( dp,0,sizeof( dp ) );
         for( int i=1;i<=n;i++ ){
             for( int j=0;j<=sum;j++ ){
                 int cnt = 0;
                 for( int k=1;k<=i;k++ ){
                     cnt += a[ i+1-k ];
                     if( cnt>j ) break;
                     dp[i][j] = max( dp[i][j],dp[i-k][j-cnt]+k*k );
                 }
                 dp[i][j] = max( dp[i][j],dp[i-1][j] );
                 ans = max( ans,dp[i][j] );
             }
         }
         printf("%d\n",ans);
     }
     return 0;
 }

 

解题转自:http://www.cnblogs.com/justforgl/archive/2013/08/13/3256043.html


  1. 嗯 分析得很到位,确实用模板编程能让面试官对你的印象更好。在设置辅助栈的时候可以这样:push时,比较要push的elem和辅助栈的栈顶,elem<=min.top(),则min.push(elem).否则只要push(elem)就好。在pop的时候,比较stack.top()与min.top(),if(stack.top()<=min.top()),则{stack.pop();min.pop();},否则{stack.pop();}.