题目
传送门:QWQ
分析
听说是水题,但还是没想出来。
$ dp[i] $为$ [1,i] $的需要的喷头数量。
那么$ dp[i]=min(dp[j])+1 $其中$ j<i $
这是个$ O(n^2)$的东西,用单调队列优化一下就行了
复杂度$ O(L) $
代码
在POJ上交的话要改一下头文件,推荐去BZOJ上交
#include <bits/stdc++.h>
using namespace std;
const int maxn=;
int dp[maxn], w[][];
int main(){
int m,s,d; scanf("%d%d%d",&s,&d,&m);
for(int i=;i<=s;i++)
for(int j=;j<=d;j++) scanf("%d",&w[i][j]); int ans=m;
for(int k=;k<d;k++){
int Max=; memset(dp,,sizeof(dp));
for(int i=;i<=s;i++)
for(int j=w[i][k];j<=ans;j++){
dp[j]=max(dp[j],dp[j-w[i][k]]+w[i][k+]-w[i][k]);
Max=max(Max,dp[j]);
}
ans+=Max;
}
printf("%d\n",ans);
return ;
}