HNU 12961 BitTorrent DP

题意：

　　你在网上下载东西，一个文件存储在一段或者多段里面，问怎么选择能在规定的流量内下载最多的文件数量。每段的大小一样。

思路：

　　习惯了做答案保存在DP数组里的题，做这种答案保存在下标里的题，转不过弯来。开始想过背包，但是一来内存不够，二来时间也不够。

　　其实是这样做的，dp[i][j][0/1]保存枚举到第i个，下载了j个，最后一个是否被下载的最小花费。 最后找花费没超过限制的最大值就好了。

　　最后值得注意的是，最后一段的时候，可能不会被p整除，不要算多了哦。

代码：

　　

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <functional>
#include <cctype>
#include <time.h>

using namespace std;

const int INF = 1<<30;
const int MAXN = 3055;

int dp[MAXN][MAXN][2]; //dp[i][j][k] 表示取到第i个，取了j个，的时候，第i个取或者不取
int a[MAXN];
int sum[MAXN]; //前缀和
int n, p, l;

int main() {
    #ifdef Phantom01
        freopen("HNU12961.in", "r", stdin);
    #endif //Phantom01

    while (scanf("%d%d%d", &n, &p, &l)!=EOF) {
        if (n==0&&p==0&&l==0) break;

        sum[0] = 0;
        for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
        for (int i = 1; i <= n; i++) sum[i] = sum[i-1]+a[i];
        for (int i = 0; i <= n; i++)
            for (int j = 0; j <= n; j++)
                dp[i][j][0] = dp[i][j][1] = INF;
        dp[0][0][0] = 0;

        for (int i = 1; i <= n; i++) {
            for (int j= 0; j <= i; j++)
                dp[i][j][0] = min(dp[i-1][j][0], dp[i-1][j][1]);
            for (int j = 1; j <= i; j++)
                dp[i][j][1] = min(dp[i-1][j-1][0]-(sum[i-1]/p)*p,
                                  dp[i-1][j-1][1]-((sum[i-1]+p-1)/p)*p)
                              + (i==n ? sum[i] : ((sum[i]+p-1)/p)*p);
        }
        int ans = 0;
        for (int i = 0; i <= n; i++)
            if (dp[n][i][0]<=l || dp[n][i][1]<=l)
                ans = max(ans, i);
        printf("%d
", ans);
    }

    return 0;
}