总钓鱼时间H，每个鱼塘当前的鱼，以及该鱼塘钓鱼了多久
首先对于位置X，并不知道最后要钓哪几个河流，那么这时候显然可以枚举
接下来分析每个鱼塘钓鱼的时间实际上就是钓鱼的次数由于如果当前确定了钓鱼的小岛个数
那么钓鱼的总时间是H-sgma(Ti),又由于对一个点的钓鱼次数对于其他点是不影响的
那么这个问题就是D = d1 + d2 +...di;是每个点的钓鱼次数，那么问题转换下
因为一共可以钓鱼(H-sgma(T)/5次，那么对于每一次的选择可以随机在每个位置
记录了每个位置的钓鱼次数，将这些次数按照每个位置进行分组，最后和仍然是总次数
同时也是从1到X的顺序进行钓鱼的，所以每一次随机选择是合理的。
贪心思路:既然每一次随机选择合理那么每一次选择的位置如何确定，我们设想每一次选择
当前可以钓的最多的鱼的位置，那么如何确定正确性。假设第一个时刻最多的鱼位置xi
若开始没有选择此位置，并假设得到了一个最优的策略，若该策略中中途含有位置xi的第一次，
那么交换该时刻与第一时刻那么最终结果是相同那么也复合最优策略。若后面不含有第一时刻的最优位置。
那么得到的个数显然比当前最优策略高所以该问题满足贪心策略
但是这题也可以采用动规的思想
148K 313MS
#include <iostream>
#include <set>
#include <algorithm>
using namespace std;
#define I64 long long
#define unt unsigned int
#define CH (ch = getchar())
#define Pt set<int>::iterator
#define For(i,a,b) for(int i=a;i<=b;++i)
#define Rep(i,a,b) for(int i=a;i>=b;i--)
#define MAX(x,y) (((x)>(y)) ? (x) : (y))
#define MIN(x,y) (((x) < (y)) ? (x) : (y))
#define MAX_N 30
static int N,h;
static struct lake
{
int i,di,ut;
}d[MAX_N];
static int f[MAX_N];
static int t[MAX_N];
static int tt[MAX_N];//到达第i个岛屿的时候路途时间
static int cmp(lake&ls,lake&rs)
{
return (ls.di>rs.di)||(ls.di==rs.di&&ls.i<rs.i);
}
static void work()
{
int ans = -999;
int s = 0;
int bestut[MAX_N] = {};
For(i,1,N)//选择最后到达的岛屿是哪一个
{
int usect[MAX_N]={};
int p = tt[i];//当前路上总时间
int k = (h*60 -p)/5;//可以钓鱼的次数
int ct = 0;
lake dt[MAX_N];
For(j,1,i)dt[j].di = d[j].di,dt[j].i = d[j].i,dt[j].ut = 0;
For(j,1,k)
{
sort(dt+1,dt+i+1,cmp);
ct+= dt[1].di;
if (dt[1].di-f[dt[1].i]<0)
dt[1].di = 0;
else
dt[1].di -= f[dt[1].i];
dt[1].ut++;
}
if (ans<ct)
{
ans = ct;
For(j,1,i)usect[dt[j].i] = dt[j].ut;
s = i;
memcpy(bestut,usect,sizeof(usect));
}
}
For(i,1,N)
{
if (i==N)
printf("%d\n",bestut[i]*5);
else
printf("%d, ",bestut[i]*5);
}
printf("Number of fish expected: %d\n",ans);
printf("\n");
}
int main()
{
while(scanf("%d",&N)&&N)
{
scanf("%d",&h);
memset(f,0,sizeof(f));
memset(t,0,sizeof(t));
memset(tt,0,sizeof(tt));
For(i,1,N)
scanf("%d",&d[i].di),d[i].i = i,d[i].ut = 0;
For(i,1,N)scanf("%d",&f[i]);
int sumt = 0;
tt[1] = 0;
For(i,2,N)
{
scanf("%d",&t[i-1]);
sumt+=5*t[i-1];
tt[i] = sumt;
}
work();
}
return 0;
}
若用dp的方法那么就需要记录当前fish[i][j]=Max{fish[i-1][j-k-t[i]],fish[i][j]+sum}
就是到达第i个点的时候总共用的总次数，类比多重背包但是注意每一次sum都是变换的根据当前
该点所用次数所以需要枚举前面I-1个点总共用过的总次数至于每个点的个数就用路径还原的方法，用递归或者用path记录都行
static void find_Path(int i, int time){
if(i==0) return;
int summ=0;
for(int k=0; k<=12*h; ++k){
if(fish[i-1][time-k-t[i-1]]+summ==fish[i][time]){
path[i]=k*5;
return find_Path(i-1,time-k-t[i-1]);
}
if (f[i]-k*d[i]>0)
summ=f[i]*(k+1)-(k+1)*k/2*d[i];
}
return;
}
static void get_DP(){
fish[0][0]=0;
for(int i=0; i<=n-1; ++i)//到达i的时候
for(int j=0; j<=12*h; ++j){//总共可以选择的次数
int summ=0;
for(int k=0; k<=12*h && fish[i][j]!=-1; ++k){//下一地点可以选择的次数
if(j+k+t[i]<=12*h)
fish[i+1][j+k+t[i]]=max(fish[i+1][j+k+t[i]],fish[i][j]+summ);
else
break;
if (f[i+1]-k*d[i+1]>0)//当前点次数增加
summ=f[i+1]*(k+1)-(k+1)*k/2*d[i+1];
}
}
maxx=0;
k=1;
for(int i = 1; i <= n; ++i)
if(maxx<fish[i][12*h])
{
maxx=fish[i][12*h];
k=i;
}
}