codeforces 19B Checkout Assistant DP

题意：一个人在超市偷东西，一秒偷一件，求最小花费

思路：dp[i]表示拿走i件物品的最小花费，那么答案就是dp[n]

dp[i]=min(dp[i],dp[i-t[j]-1]+c[j]);

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <map>
#include <string>
using namespace std;
#define eps 1e-8
#define LL long long
LL dp[2005];
LL t[2005],c[2005];
int main()
{
    int T,i,j,k,m,n,ans,a,b;
    while(scanf("%d",&n)!=EOF)
    {
        for(i=0;i<=2000;i++)
            dp[i]=9999999999999;
        for(i=0; i<n; i++)
        {
            scanf("%lld%lld",&t[i],&c[i]);
            t[i]++;
        }
        dp[0]=0;
        for(i=0; i<n; i++)
        {
            for(j=n;j>=0;j--)
            {
                if(j-t[i]<0) dp[j]=min(dp[j],c[i]);
                else dp[j]=min(dp[j],dp[j-t[i]]+c[i]);
            }
        }
        printf("%lld
",dp[n]);
    }
    return 0;
}