HDU 3646 DP+二分

リンク:http://acm.hdu.edu.cn/showproblem.php?pid=3646
标题:あなたはN本の武器を持っていて、すべての武器は敵人に対して一定の傷害をもたらすことができ(et:攻撃力500、敵の血量は200で、敵を殺して、攻撃力は残り300)、全部でK個の敵がいて、あなたはM回の魔法double武器の攻撃力(倍)があって、武器を使うのは規則があります:武器は2つの状態があって、1つの状態はyoung、1つはold、新しい武器の状態はyoungで、あなたがそれを使って1人の敵を殺した後に、状態はoldになって、状態がyoungの時、たとえこの武器の残りの攻撃力が現在の敵を殺すのに足りないとしても、しかし彼の一定の血量を傷つけることができて、しかしoldの時、武器の攻撃力が相手を殺すのに足りなければ、彼を攻撃することはできません(例えば攻撃力が200で、敵の血量が500で、young:敵は200を減らして、old:敵の血量は減らない).武器の使用順序と殺人の順序は与えられている.最大何人殺すことができますか?
見解:old,youngがなければ、これは水DPであり、この状態があれば、私たちは処理しにくい.主に現在の武器の状態が何なのか分からない.もし1次元を加えて現在の状態を表すと、もう1次元表示が何番目の敵に挑戦しているのか、私たちはこのように状態を理解することができる.dp【i】【j】表示使用完i把武器,用了j次魔法,全部造成的伤害是多少,转移时,两分钟下现在的伤害可以知道现在在杀第a个人,然后二分再用一把武器,アディダススニーカー,可以知道挑战到第b个人,如果两人不是同一个人,那就不能伤害b,では、この武器を使って私たちがもたらすダメージはsum【b】です.最後の2点ダメージで、最大何人かを殺すことができます.コードを詳しく見てください.

#include<stdio.h>
#include<string.h>
#include<algorithm>
#define Max(a,b) ((a)>(b)?(a):(b))
using namespace std;
const int maxn = 105;
const int maxm = 100005;
int dp[2][maxn],life[maxm],power[maxn * maxn],N,M,K;
int sum[maxm];
int main()
{
    int cnt = 0;
    while(scanf("%d%d%d",&N,&M,&K) && N + M + K)
    {
        for(int i = 1;i <= N;i ++) scanf("%d",&power[i]);
        for(int i = 1;i <= K;i ++)
        {
            scanf("%d",&life[i]);
            sum[i] = sum[i - 1] + life[i];
        }
        int ans = 0;
        M = min(M,N);
        memset(dp,0,sizeof(dp));
        for(int i = 1;i <= N && !ans;i ++)
        {
            for(int j = 0;j <= M;j ++)
            {
                int a , b, next_a,next_b;
                a = upper_bound(sum + 1,sum + 1 + K,dp[(i - 1) & 1][j]) - sum;// now killed
                if(j)
                {
                    b = upper_bound(sum + 1,sum + 1 + K,dp[(i - 1) & 1][j - 1]) - sum;//now killed j - 1
                    next_b = upper_bound(sum + 1,sum + 1 + K,dp[(i - 1) & 1][j - 1] + (power[i] << 1)) - sum;// use power
                }
                next_a = upper_bound(sum + 1,sum + 1 + K,dp[(i - 1) & 1][j] + power[i]) - sum;//not use power
                int hurt_a = dp[(i - 1) & 1][j] + power[i],hurt_b ;
                if(a != next_a) hurt_a = sum[next_a - 1];
                if(j) hurt_b = dp[(i - 1) & 1][j - 1] + (power[i] << 1);
                if(j) if(b != next_b) hurt_b = sum[next_b - 1];
                if(j)dp[i & 1][j] = Max(hurt_a,hurt_b);
                else dp[i & 1][j] = hurt_a;
                if(dp[i & 1][j] >= sum[K])
                {
                    ans = K;
                    break;
                }
            }
        }
        if(!ans) ans =  upper_bound(sum + 1,sum + 1 + K,dp[N & 1][M]) - sum - 1;
        printf("%d
",ans);
    }
    return 0;
}