The Imp
Problem's Link: http://acm.hnu.cn/online/?action=problem&type=show&id=13404&courseid=0
Mean:
n个物品，每个物品价值为v，价格为c，你只可以带一个物品离开。
有一个精灵，它可以施法让你购买后的物品价值变为0(未离开商店之前)，精灵最多施k次法术。
你的目的是让自己获得最大收益，而小鬼的目的正好相反。
如果你和精灵都采用最优策略，最后你可以盈利多少？
analyse:
第一感觉是三维dp，然而三维肯定会超时超内存。
然后就是想怎样压缩状态。。。
想了想其实两维就够了，为什么呢？因为对于第i件物品，如果我不选，那么它这次施不施法是没有影响的。
dp[i][j]：判断到第i个物品，精灵施了j次魔法，我还能获得的最大收益。
状态转移方程：dp[i][j]=max(dp[i-1][j],min(dp[i-1][j-1]-c,v-c))
伪代码：
for_each
i
{
if( select i)
{
for_each j
{
if( magic j time)
{
max( before i) - cost;
}
else
{
value - cost;
}
}
}
else
{
max( before i);
}
}
{
if( select i)
{
for_each j
{
if( magic j time)
{
max( before i) - cost;
}
else
{
value - cost;
}
}
}
else
{
max( before i);
}
}
Time complexity: O(N*K)
Source code:
/*
* this code is made by crazyacking
* Verdict: Accepted
* Submission Date: 2015-08-15-12.09
* Time: 0MS
* Memory: 137KB
*/
#include <queue>
#include <cstdio>
#include <set>
#include <string>
#include <stack>
#include <cmath>
#include <climits>
#include <map>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#define LL __int64
#define ULL unsigned long long
using namespace std;
const LL MAXN = 200010;
struct node
{
LL v , c;
bool operator <( const node & a) const
{
return v > a . v;
}
} a [ MAXN ];
LL dp [ MAXN ][ 10 ];
int main()
{
ios_base :: sync_with_stdio( false);
cin . tie( 0);
LL Cas;
scanf( "%I64d" , & Cas);
while( Cas --)
{
LL n , k;
scanf( "%I64d %I64d" , &n , & k);
for( LL i = 1; i <=n; ++ i)
{
scanf( "%I64d %I64d" , & a [ i ]. v , & a [ i ]. c);
}
sort( a + 1 , a +n + 1);
LL ans = 0 , val;
memset( dp , 0 , sizeof dp);
for( LL i = 1; i <=n; ++ i)
{
val = a [ i ]. v - a [ i ]. c;
dp [ i ][ 0 ] = max( dp [ i - 1 ][ 0 ], val);
for( LL j = 1; j <= k; ++ j)
{
dp [ i ][ j ] = max( dp [ i - 1 ][ j ], min( dp [ i - 1 ][ j - 1 ] - a [ i ]. c , val));
}
ans = max( ans , dp [ i ][ k ]);
}
printf( "%I64d \n " , ans);
}
return 0;
}
/*
*/
* this code is made by crazyacking
* Verdict: Accepted
* Submission Date: 2015-08-15-12.09
* Time: 0MS
* Memory: 137KB
*/
#include <queue>
#include <cstdio>
#include <set>
#include <string>
#include <stack>
#include <cmath>
#include <climits>
#include <map>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#define LL __int64
#define ULL unsigned long long
using namespace std;
const LL MAXN = 200010;
struct node
{
LL v , c;
bool operator <( const node & a) const
{
return v > a . v;
}
} a [ MAXN ];
LL dp [ MAXN ][ 10 ];
int main()
{
ios_base :: sync_with_stdio( false);
cin . tie( 0);
LL Cas;
scanf( "%I64d" , & Cas);
while( Cas --)
{
LL n , k;
scanf( "%I64d %I64d" , &n , & k);
for( LL i = 1; i <=n; ++ i)
{
scanf( "%I64d %I64d" , & a [ i ]. v , & a [ i ]. c);
}
sort( a + 1 , a +n + 1);
LL ans = 0 , val;
memset( dp , 0 , sizeof dp);
for( LL i = 1; i <=n; ++ i)
{
val = a [ i ]. v - a [ i ]. c;
dp [ i ][ 0 ] = max( dp [ i - 1 ][ 0 ], val);
for( LL j = 1; j <= k; ++ j)
{
dp [ i ][ j ] = max( dp [ i - 1 ][ j ], min( dp [ i - 1 ][ j - 1 ] - a [ i ]. c , val));
}
ans = max( ans , dp [ i ][ k ]);
}
printf( "%I64d \n " , ans);
}
return 0;
}
/*
*/
