【URAL 1917】Titan Ruins: Deadly Accuracy(DP)

题目

#include<cstdio>
#include<algorithm>
using namespace std;
#define N 1005
int n, m, cnt;
int a[N], b[N], dp[N]; //dp[i]表示到a[i]大的怪物都死最少要多少个spell
int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
        dp[i] = 0x3f3f3f3f;
    }
    sort(a + 1, a + 1 + n);
    for(int i = 1; i <= n; i++)
    {
        if(a[i] != a[cnt]) //记下每个不同值
            a[++cnt] = a[i];
        b[cnt] = i; //第cnt个持续到第i位
    }
    for(int i = 1; i <= cnt; i++) //用大小为a[i]的spell
        for(int j = 0; j < i; j++) //小于等于a[j]的怪物在前面已经打败了的情况
            if((b[i] - b[j]) * a[i] <= m)
                dp[i] = min(dp[i], dp[j] + 1); //a[j+1]到a[i]的怪物都是这个spell打败的
    for(int i = cnt; i; i--)
        while(dp[cnt] == 0x3f3f3f3f) cnt--;
    printf("%d %d", b[cnt], dp[cnt]);
    return 0;
}