分别枚举矩形的上下边,把问题转化为求一维的最大子段。

枚举+贪心
把每钓5分钟鱼称为钓一次鱼。首先枚举John需要走过的池塘的数目X，即从池塘1走到池塘X。减去路上花去的时间T=sum(Ti) i=1...X-1，这样我们可以认为John能从一个池塘"瞬间转移"到另一个池塘，即在任意一个时刻都可以在池塘1到池塘X中任选一个钓一次鱼(很重要)。现在采用贪心策略，每次选择鱼最多的池塘钓一次鱼。对于每个池塘来说，由于在任何时候鱼的数目只和John在该池塘里钓鱼的次数有关，和钓鱼的总次数无关，所以这个策略是最优的。假设一共允许钓k次鱼，那么每次在N个池塘中选择鱼最多的一个钓。总的时间复杂度为O(kn^2)。 在最后的结果中，第一个最大值所对应的在每个池塘的钓鱼时间为题目要求的情况，因为如果John在后面的池塘钓了鱼，那么前面相应的时间就会减少。最后注意池塘中没有鱼的情况。

#include<iostream>
using namespace std;
int n,h,ans;
int f[26],t[26],d[26];
int main()
{
    int i,k,total,j=0;
    int fish[26],time[26],tt[26];
    while(scanf("%d",&n)!=EOF&&n)
    {
        scanf("%d",&h);
        h*=12;
        for(i=1;i<=n;i++) scanf("%d",&f[i]);
        for(i=1;i<=n;i++) scanf("%d",&d[i]);
        t[1]=0;
        for(i=2;i<=n;i++)
        {
            scanf("%d",&t[i]);
            t[i]+=t[i-1];
        }
        ans=-1;
        for(i=1;i<=n;i++)
        {
            total=0;
            int remain=h-t[i];
            memcpy(fish,f,sizeof(f));
            memset(tt,0,sizeof(tt));
            while(remain>0)
            {
                int maxn=-1,cur=-1;
                for(k=1;k<=i;k++)
                {
                    if(fish[k]>maxn)
                    {
                        maxn=fish[k];
                        cur=k;
                    }
                }
                total+=maxn;
                fish[cur]-=d[cur];
                if(fish[cur]<0) fish[cur]=0;
                tt[cur]+=5;
                remain--;
            }
            if(total>ans)
            {
                ans=total;
                memcpy(time,tt,sizeof(tt));
            }
        }
        if(j) printf("\n");
        j=1;
        for(i=1;i<=n;i++)
        {
            if(i==n) printf("%d \n",time[i]);
            else printf("%d, ",time[i]);
        }
        printf("Number of fish expected: %d\n",ans);
    }
    return 0;
}

     摘要: 刚学编程的时候写的，留下来做个纪念。一、初步设计1、新建工程slidwindow，在MFC的向导第一步选择Single Document，按Finish结束。2、选择ResourceView窗口，打开菜单编辑器，在顶层菜单上添加“开始”和“单步”菜单，其ID分别为ID_START_SLIDWIND和ID_TRACE_SLIDWIND，在 &...  阅读全文

做该题的时候,看了网上另外一个版本的递推关系,不过还是朴素一点的比较好理解.状态转移方程为:
f[i,j]=max{f[i-1,j-1],f[i-1,j],f[i-1,j+1]}+w(i,j), 其中f[i,j]表示第i 秒 ,门开放度为j 时的最大加分.w(i,j)表示在该状态下的所有加分.为防止超内存用滚动数组.(由于不仔细把1写成了i,调试了半天,杯具了~~)  详细见代码:

一道很经典的DP，状态转移方程为：f[i,j,k]=max{f[i-1,j,k],f[i-1,j-1,k-(p[i]-d[i])]+p[i]+d[i]}。其中f[i,j,k]表示在前i个候选人中选择j个人,并且辩控差为k时的最大辩控和。另外用path[i,j,k]来记录路径，表示当前方案下选择的最后一个人。详细见代码：

首先建一个虚结点,权值为无穷大.  将入度为0的点与之相连, 然后做树形DP,为了防止重复,父亲单独考虑.详细见代码:

     摘要: 树形背包。代码如下： #include<iostream>#include<vector>using namespace std;int n,m;int num[105],brain[105];int dp[105][105];int vis[105];vector<int> map[105...  阅读全文

依赖背包(树形背包)。见代码：