题目大意:
FJ的N ( 1 < = N < = 5,000)头奶牛不喜欢被淋湿。它们站在数轴上(1到M ( 1 < = M < = 100,000 )),现在FJ要买伞,遮住i个点的伞要Ci元,问给所有的牛遮雨要花多少钱?
输入数据
第1行:两个用空格隔开的整数: N和M
这题就是一道裸dp,先按坐标排序 然后记f[i]表示覆盖前i个牛需要多少钱 f[i]=min{f[j-1]+cost[a[i]-a[j]+1]) 1<=j<=i
附代码
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> const int maxn=5010,maxm=100010; using namespace std; #ifdef judgeonline const int maxchar=20000000; char buf[maxchar],*wbuf=buf; inline int getint(){ int tmp=0; while (*wbuf<'0' || *wbuf>'9') ++wbuf; for (;*wbuf>='0' && *wbuf<='9';++wbuf) tmp=tmp*10+*wbuf-'0'; return tmp; } #else inline int getint(){ char ch=getchar(); int tmp=0; while (ch<'0' || ch>'9') ch=getchar(); for (;ch<='9' && ch>='0';ch=getchar()) tmp=tmp*10+ch-'0'; return tmp; } #endif int n; int wh[maxn]; int price[maxm]; void init(){ n=getint(); int m=getint(); for (int i=1;i<=n;++i) wh[i]=getint(); for (int i=1;i<=m;++i) price[i]=getint(); for (int i=m-1;i>=1;--i) price[i]=min(price[i],price[i+1]); } int f[maxn]; void dp(){ sort(wh+1,wh+n+1); memset(f,63,sizeof(f)); f[0]=0; for (int i=1;i<=n;++i) for (int j=1;j<=i;++j) f[i]=min(f[i],f[j-1]+price[wh[i]-wh[j]+1]); printf("%d\n",f[n]); } int main(){ init(); dp(); return 0; }
Ps:这题有个坑爹的地方,就是有可能越长越便宜,然后就Wa了2次。。。