收銀員

題目大意：

有n件物品，每件物品有他的掃描時間和價格，在掃描的時候可以偷物品（一個單位時間偷一件），問最少給多少錢

原題：

解題思路：

設f[j]為偷或買共j件花的最少錢，就得出$f[j]=min(f[j],f[j?t?1]+c)$,再減一是買了的一個，要么就對于j<t的就是$f[j]=min(f[j],c)$

代碼：

#include<cstdio> #include<iostream> #include<cstring> using namespace std; int n,t; long long c,f[2005]; int main() {scanf("%d",&n);for (int i=1;i<=n;++i)f[i]=1<<30;//一個很大的值for (int i=1;i<=n;++i){scanf("%d %lld",&t,&c);for (int j=n;j>t;--j)f[j]=min(f[j],f[j-t-1]+c);//前面買過，再一次買for (int j=1;j<=t;++j)f[j]=min(f[j],c);//前面沒買過，直接買}printf("%lld",f[n]); }

總結

以上是生活随笔為你收集整理的【DP】收银员的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。