【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 = ; i <= n; i++)
{
scanf("%d", &a[i]);
dp[i] = 0x3f3f3f3f;
}
sort(a + , a + + n);
for(int i = ; i <= n; i++)
{
if(a[i] != a[cnt]) //记下每个不同值
a[++cnt] = a[i];
b[cnt] = i; //第cnt个持续到第i位
}
for(int i = ; i <= cnt; i++) //用大小为a[i]的spell
for(int j = ; j < i; j++) //小于等于a[j]的怪物在前面已经打败了的情况
if((b[i] - b[j]) * a[i] <= m)
dp[i] = min(dp[i], dp[j] + ); //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 ;
}
  
上一篇:现代程序设计homework-06


下一篇:redis redis常用命令及内存分析总结(附RedisClient工具简介