P10884 [COCI 2017-2018#2] San
题目传送门:P10884 [COCI 2017-2018#2] San
看下标签
COCI(克罗地亚) 2017
啊
比我小4年的题
分析
定义 dp[i][j] 表示从第 i 栋楼开始,获得至少 j 个金币的方案数。
初始时,dp[i][j] = 1 当且仅当 G_i \geq j。
然后,我们可以从右往左依次计算每个 dp[i][j] 的值。
对于当前的 dp[i][j],我们需要计算它的子问题 dp[k][j] 的值,并累加到 dp[i][j] 上。其中,k > i 且 H_k \geq H_i。
最终,我们要求的答案就是 dp[1][K] 的值
时间复杂度就是是 O(N^2K)
为什么博客园不支持Latex!好难受啊
Code
#include<bits/stdc++.h>
using namespace std;
long long mx[45];
long long way[45];
int n;long long K;
struct Build
{
int h,v;
}edge[45];
long long ans;
void dfs(int now,long long tot)
{
if(tot>=K) {ans+=way[now];return ;}
if(now==n+1) return ;
for(int i=now+1;i<=n;i++)
{
if(edge[i].h>=edge[now].h)
{
if(tot+mx[i]<tot) continue;
dfs(i,tot+edge[i].v);
}
}
}
int main()
{
scanf("%d%lld",&n,&K);
for(int i=1;i<=n;i++) {scanf("%d%d",&edge[i].h,&edge[i].v);}
mx[n]=edge[n].v;way[n]=1;
for(int i=n-1;i>=1;i--)
{
for(int j=i+1;j<=n;j++)
{
if(edge[i].h<=edge[j].h) mx[i]=max(mx[i],mx[j]),way[i]+=way[j];
}
mx[i]+=edge[i].v;way[i]++;
}
for(int i=1;i<=n;i++)
dfs(i,edge[i].v);
printf("%lld\n",ans);
return 0;
}
为什么是120分啊