许久不见动态规划,没想到数模碰到了,就想水篇久违的题解。

至于为什么不放完整论文?肯定是做的不是很好啦,话说原来数模出题人也会是ACMer吗

穿越沙漠

题意

​ 考虑如下的小游戏:玩家凭借一张地图,利用初始资金购买一定数量的水和食物(包括食品和其他日常用品),从起点出发,在沙漠中行走。途中会遇到不同的天气,也可在矿山、村庄补充资金或资源,目标是在规定时间内到达终点,并保留尽可能多的资金。

游戏的基本规则如下:

(1)以天为基本时间单位,游戏的开始时间为第0天,玩家位于起点。玩家必须在截止日期或之前到达终点,到达终点后该玩家的游戏结束。

(2)穿越沙漠需水和食物两种资源,它们的最小计量单位均为箱。每天玩家拥有的水和食物质量之和不能超过负重上限。若未到达终点而水或食物已耗尽,视为游戏失败。

(3)每天的天气为“晴朗”、“高温”、“沙暴”三种状况之一,沙漠中所有区域的天气相同。

(4)每天玩家可从地图中的某个区域到达与之相邻的另一个区域,也可在原地停留。沙暴日必须在原地停留

(5)玩家在原地停留一天消耗的资源数量称为基础消耗量,行走一天消耗的资源数量为基础消耗量的2倍

(6)玩家第0天可在起点处用初始资金以基准价格购买水和食物。玩家可在起点停留或回到起点,但不能多次在起点购买资源。玩家到达终点后可退回剩余的水和食物,每箱退回价格为基准价格的一半

(7)玩家在矿山停留时,可通过挖矿获得资金,挖矿一天获得的资金量称为基础收益。如果挖矿,消耗的资源数量为基础消耗量的3倍;如果不挖矿,消耗的资源数量为基础消耗量。到达矿山当天不能挖矿。沙暴日也可挖矿。

(8)玩家用剩余的初始资金或挖矿获得的资金在村庄去其他地方是可以购买水和食物,每箱价格为基准价格的2倍

请根据游戏的设定,假设只有一名玩家,在整个游戏时段内每天天气状况事先全部已知,试给出一般情况下玩家的最优路径。

最优解为到终点还有10470金钱,用时24天

最优解为到终点时还有12730金钱,用时30天

思路

很明显的一个动态规划

设状态dp[k][j][w][f]代表第k天时在第j个点剩余水为w箱剩余食物为f箱的最大资金,则:

就是遍历第每天在终点的所有水、食物的状态求最大值。

初始值设定

由于起始点可以在起点购买物资,则有初始状态:

其中$cost_water$​​,$cost_food$​​​​ 为购买水和食物消耗的钱。

这里假设起始为第0天,则第一天天气影响的是从第0天到第1天。

状态转移方程

当第k天人在村庄j时:

  • 第k天为沙暴天气:

    dp[k+1][j][w+ww-xh_water[tq]][f+ff-xh_food[tq]]}=max(dp[k][j][w][f]-2*ww*cost_water-2*ff*cost_food

  • 非沙暴天气:

    ​ 从j点走到jj点

    dp[k+1][jj][w+ww-xh_water[tq]][f+ff-xh_food[tq]]}=max(dp[k][j][w][f]-2*ww*cost_water-2*ff*cost_food

当第k天人在矿山j时:

  • 挖矿:

    dp[k+1][j][w-dig*xh_water[tq]][f-dig*xh_food[tq]]=max(dp[k][j][w][f]+1000)

  • 第k天为沙暴天气:

    dp[k+1][j][w-xh_water[tq]][f-xh_food[tq]]=max(dp[k][j][w][f])

  • 第k天为非沙暴天气:

    dp[k+1][jj][w-walk*xh_water[tq]][f-walk*xh_food[tq]]=max(dp[k][jj][w][f])

当第k天人在其他地区时

  • 第k天为沙暴天气:

    dp[k+1][j][w-xh_water[tq]][f-xh_food[tq]]=max(dp[k][j][w][f])

  • 第k天为非沙暴天气:

    ​ 从j点走到jj点

    dp[k][jj][w-walk*xh_water[tq]][f-walk*xh_food[tq]]=max(dp[k][j][w][f])

优化

​ 虽然没有评测姬,但是作为曾经的Acmer不能容忍运行样例大于1s,所以只会转移方程还是过不了这题。

显然由样例可知,点 太 多 了!!!,我们考虑删点。

稍微思考一下就知道这题有几个隐含条件:

  • 除了回村庄补充物资,不会走回头路。
  • 除了挖矿和沙尘暴不会在原地停留。
  • 只会走关键点之间的最短路径

故我们只需要将关键点之间的最短路求出,最短路经过的点才被认为是有效点,最短路经过的边才被认为是有效边,这样就可以化简图了。

化简之后的路径图如下:

image-20210818175743599

​ 可见有效点只有10个大大减少了时间复杂度,但是点数超过13仍会爆空间和时间,空间可以试试滚动数组优化,时间我是没什么好办法了。

代码

第一关

代码

#include<bits/stdc++.h>
#include<iostream>
using namespace std;

// 点数
const int N=11,M=28,inf=0x3f3f3f,Day=30;
int dp[32][N+1][405][605],zd,qd,FZ;
int cost_water,cost_food,walk,dig,buy;
int xh_water[3]={5,8,10},xh_food[3]={7,6,10};
bool cz[N+1],ks[N+1];

struct node
{
short day; // i
short from; // jj j
int water,food;
int money;
bool operator!=(const node &x){
return x.day!=day || x.from!=from || x.water!=water || x.food!=food ;
};
}path[31][N+1][405][605],lastpath;
vector <int> weather;
vector <int> g[N];
map <int,int> mp;
void push_back(int x,int y)
{
g[x].push_back(y);
g[y].push_back(x);
}

void build_map()
{
push_back(1,2);
push_back(2,3);
push_back(2,5);
push_back(5,6);
push_back(3,4);
push_back(4,7);
push_back(6,7);
push_back(7,8);
push_back(8,9);
push_back(9,10);
push_back(10,11);

mp[1]=1;
mp[2]=25;
mp[3]=26;
mp[4]=27;
mp[5]=24;
mp[6]=23;
mp[7]=21;
mp[8]=9;
mp[9]=15;
mp[10]=14;
mp[11]=12;
for(int i=1;i<=N;i++)
{
cz[i]=0;
ks[i]=0;
}
cz[9]=1;
ks[11]=1;
zd=4;
qd=1;

return ;
}
void init()
{
memset(dp,-inf,sizeof(dp));
FZ=1200;
cost_water=5;
cost_food=10;

walk=2;
buy=2;
dig=3;


for(int k=0;k<=405;k++)
{
for(int l=0;l<=601;l++)
{
if(k*3+l*2<=FZ)
{
dp[0][qd][k][l]=10000-k*cost_water-l*cost_food;
}
}
}
printf("init %d\n",dp[0][1][178][333]);
path[0][1][0][0]={0,0,0,0};
return ;
}
int main()
{

weather={
1,1,0,2,0,1,2,0,1,1,
2,1,0,1,1,1,2,2,1,1,
0,0,1,0,2,1,0,0,1,1,
};

build_map();
init();
for(int i=0;i<Day;i++)
{
printf("第%d天\n",i);
int tq=weather[i];
for(int j=1;j<=N;j++)
{
if(cz[j])// 村庄
{
for(int w=0;w<=405;w++)
{
for(int f=0;w*3+f*2<=1200;f++)
{
//购买或不够买物资(ww=0,ff=0就是不购买)
if(tq==2) //停留
{
int money=dp[i][j][w][f];
for(int ww=0;ww<=money/cost_water;ww++)
{
for(int ff=0;ff<=(FZ-(w+ww)*3)/2-f;ff++)
{

if(w+ww-xh_water[tq]>=0&&f+ff-xh_food[tq]>=0&&dp[i][j][w][f]-2*ww*cost_water-2*ff*cost_food>=0)
{
if(dp[i+1][j][w+ww-xh_water[tq]][f+ff-xh_food[tq]]<dp[i][j][w][f]-2*ww*cost_water-2*ff*cost_food)
{
dp[i+1][j][w+ww-xh_water[tq]][f+ff-xh_food[tq]]=dp[i][j][w][f]-2*ww*cost_water-2*ff*cost_food;
path[i+1][j][w+ww-xh_water[tq]][f+ff-xh_food[tq]]={i,j,w,f,dp[i][j][w][f]-2*ww*cost_water-2*ff*cost_food};
}
}

}
}
}
else //从j走到jj
{
for(auto jj:g[j])
{
int money=dp[i][j][w][f];
for(int ww=0;ww<=money/cost_water;ww++)
{
for(int ff=0;ff<=(FZ-(w+ww)*3)/2-f;ff++)
{
if(w+ww-walk*xh_water[tq]>=0&&f+ff-walk*xh_food[tq]>=0&&dp[i][j][w][f]-buy*ww*cost_water-buy*ff*cost_food>=0)
{
if(dp[i+1][jj][w+ww-walk*xh_water[tq]][f+ff-walk*xh_food[tq]]<dp[i][j][w][f]-buy*ww*cost_water-buy*ff*cost_food)
{
dp[i+1][jj][w+ww-walk*xh_water[tq]][f+ff-walk*xh_food[tq]]=dp[i][j][w][f]-buy*ww*cost_water-buy*ff*cost_food;
path[i+1][jj][w+ww-walk*xh_water[tq]][f+ff-walk*xh_food[tq]]={i,j,w,f,dp[i][j][w][f]-buy*ww*cost_water-buy*ff*cost_food};
}

}
}
}
}
}
}
}
}
else if (ks[j])// 矿山
{
for(int w=0;w<=405;w++)
{
for(int f=0;w*3+f*2<=1200;f++)
{
// 已经停留一天了,可以挖矿
if(w-dig*xh_water[tq]>=0&&f-dig*xh_food[tq]>=0)
{
if(dp[i+1][j][w-dig*xh_water[tq]][f-dig*xh_food[tq]]<dp[i][j][w][f]+1000&&dp[i][j][w][f]>=0)
{
dp[i+1][j][w-dig*xh_water[tq]][f-dig*xh_food[tq]]=dp[i][j][w][f]+1000;
path[i+1][j][w-dig*xh_water[tq]][f-dig*xh_food[tq]]={i,j,w,f,dp[i][j][w][f]+1000};
}

}
// 在矿山不挖矿或 不允许挖矿
if(tq==2) //停留但不挖矿
{
if(w-xh_water[tq]>=0&&f-xh_food[tq]>=0)
{
if(dp[i+1][j][w-xh_water[tq]][f-xh_food[tq]]<dp[i][j][w][f]&&dp[i][j][w][f]>=0)
{

dp[i+1][j][w-xh_water[tq]][f-xh_food[tq]]=dp[i][j][w][f];
path[i+1][j][w-xh_water[tq]][f-xh_food[tq]]={i,j,w,f,dp[i][j][w][f]};
}

}
}
else
{
if(w-walk*xh_water[tq]>=0&&f-walk*xh_food[tq]>=0)
{
for(auto jj:g[j])
{
if(dp[i+1][jj][w-walk*xh_water[tq]][f-walk*xh_food[tq]]<dp[i][j][w][f]&&dp[i][j][w][f]>=0)
{
dp[i+1][jj][w-walk*xh_water[tq]][f-walk*xh_food[tq]]=dp[i][j][w][f];
path[i+1][jj][w-walk*xh_water[tq]][f-walk*xh_food[tq]]={i,j,w,f,dp[i][j][w][f]};
}

}
}
}
}
}
}
else //普通区
{
for(int w=0;w<=405;w++)
{
for(int f=0;w*3+f*2<=1200;f++)
{
if(tq==2) //在j点停留
{
if(w-xh_water[tq]>=0&&f-xh_food[tq]>=0&&dp[i][j][w][f]>=0)
{
if(dp[i+1][j][w-xh_water[tq]][f-xh_food[tq]]<dp[i][j][w][f])
{
dp[i+1][j][w-xh_water[tq]][f-xh_food[tq]]=dp[i][j][w][f];
path[i+1][j][w-xh_water[tq]][f-xh_food[tq]]={i,j,w,f,dp[i][j][w][f]};
}
}
}
else// 走到jj点
{
for(auto jj:g[j])
{
if(w-walk*xh_water[tq]>=0&&f-walk*xh_food[tq]>=0&&dp[i][j][w][f]>=0)
{
if(dp[i+1][jj][w-walk*xh_water[tq]][f-walk*xh_food[tq]]<dp[i][j][w][f])
{

dp[i+1][jj][w-walk*xh_water[tq]][f-walk*xh_food[tq]]=dp[i][j][w][f];
path[i+1][jj][w-walk*xh_water[tq]][f-walk*xh_food[tq]]={i,j,w,f,dp[i][j][w][f]};

}

}
}
}
}
}
}
}
}
int ans=-inf;
node lastpath;
int last_water=0,last_food=0,last_day=Day;
for(int i=0;i<=Day;i++)
{
for(int w=0;w<=405;w++)
for(int f=0;w*3+2*f<=1200;f++)
{
if(dp[i][zd][w][f]>ans)
{
ans=dp[i][zd][w][f];
lastpath=path[i][zd][w][f];
last_water=w;
last_food=f;
last_day=i;
}
}
}
stack<node> s;
stack<int> my;
printf("??day:%d weather:%d %d water:%d food:%d money:%d\n",last_day,weather[Day],zd,last_water,last_food,ans);
s.push((node){last_day,zd,last_water,last_food,ans});


while(lastpath!=path[0][1][0][0])
{
s.push(lastpath);
printf("??day:%d weather:%d %d water:%d food:%d money:%d\n",lastpath.day,weather[lastpath.day],mp[lastpath.from],lastpath.water,lastpath.food,lastpath.money);
my.push(lastpath.money);
lastpath=path[lastpath.day][lastpath.from][lastpath.water][lastpath.food];
}
freopen("output.txt","w",stdout);
my.push(my.top());
while (!s.empty())
{
node t=s.top();
int money=my.top();
printf("Day:%d weather:%d point:%d water:%d food:%d money:%d\n",t.day,weather[t.day],mp[t.from],t.water,t.food,money);
s.pop();
my.pop();
}
printf("%d\n",ans);
return 0;
}

结果

日期 所在区域 剩余资金数 剩余水量 剩余食物量
0 1 5780 178 333
1 25 5780 162 321
2 26 5780 146 309
3 27 5780 136 295
4 27 5780 126 285
5 21 5780 116 271
6 9 5780 100 259
7 9 5780 90 249
8 15 5780 80 235
9 14 4150 227 223
10 12 4150 211 211
11 12 5150 181 181
12 12 6150 157 163
13 12 7150 142 142
14 12 8150 118 124
15 12 9150 94 1106
16 12 10150 70 88
17 12 10150 60 78
18 12 10150 50 68
19 12 11150 26 50
20 14 11150 10 38
21 15 11150 0 24
22 9 10470 26 26
23 21 10470 10 14
24 27 10470 0 0

第二关

代码

​ 与第一关不同的是点的数量变多了,空间复杂度过不去。我只好把path删了一个变量money才勉强过去。就是后面要手算money很麻烦

​ 后来想应该可以滚动数组的,但是不想写了。毕竟已经退役了

#include<bits/stdc++.h>
#include<iostream>
using namespace std;

const short N=27,inf=20000,Day=30;
short dp[31][N+1][401][601],zd,qd,FZ;
short cost_water,cost_food,walk,dig,buy;
short xh_water[3]={5,8,10},xh_food[3]={7,6,10};
bool cz[N+1],ks[N+1];

struct node
{
char day; // i
char from; // jj j
short water,food;
bool operator!=(const node &x){
return (x.day-'0')!=(day-'0') || (x.from-'0'!=from-'0') || (x.water-'0')!=(water-'0') || (x.food-'0'!=food-'0') ;
};
}path[31][N+1][401][601],lastpath;
vector <short> weather;
vector <short> g[N+1];
map <short,short> mp;
void push_back(short x,short y)
{
g[x].push_back(y);
g[y].push_back(x);
}

void build_map(short flag)
{
if(flag==2)
{
push_back(1,2);
push_back(2,3);
push_back(3,4);
push_back(4,5);
push_back(5,6);
push_back(6,7);
push_back(7,8);
push_back(8,9);
push_back(9,10);
push_back(10,11);
push_back(11,12);
push_back(7,13);
push_back(13,14);
push_back(14,15);
push_back(15,16);
push_back(15,10);
push_back(15,11);
push_back(16,12);
push_back(3,17);
push_back(17,18);
push_back(18,19);
push_back(19,20);
push_back(20,21);
push_back(21,22);
push_back(22,23);
push_back(15,23);
push_back(23,16);

mp[1]=1;
mp[2]=2;
mp[3]=3;
mp[4]=4;
mp[5]=12;
mp[6]=21;
mp[7]=29;
mp[8]=30;
mp[9]=39;
mp[10]=47;
mp[11]=56;
mp[12]=64;
mp[13]=38;
mp[14]=46;
mp[15]=55;
mp[16]=63;
mp[17]=11;
mp[18]=20;
mp[19]=28;
mp[20]=37;
mp[21]=45;
mp[22]=54;
mp[23]=62;
for(short i=1;i<=N;i++)
{
cz[i]=0;
ks[i]=0;
}
cz[9]=cz[23]=1;
ks[8]=ks[15]=1;
qd=1;
zd=12;
}
return ;
}

void init()
{

FZ=1200;
cost_water=5;
cost_food=10;

walk=2;
buy=2;
dig=3;
for(short i=0;i<=Day;i++)
{
for(short j=1;j<=N;j++)
{
for(short w=0;w<=400;w++)
{
for(short f=0;f<=600;f++)
{
if(w*3+f*2<=FZ)
{
dp[i][j][w][f]=-inf;
}
}
}
}
}
for(short k=10;k<=405;k++)
{
for(short l=0;k*3+l*2<=FZ;l++)
{
dp[0][qd][k][l]=10000-k*cost_water-l*cost_food;
}
}
path[0][1][0][0]={0,0,0,0};
return ;
}

int main()
{

weather={
1,1,0,2,0,1,2,0,1,1,
2,1,0,1,1,1,2,2,1,1,
0,0,1,0,2,1,0,0,1,1,
};

build_map(2);
init();
// dp [i][j][w][f]
// 第i天 在j个点 w 箱水 f 箱食物 时最大利润,
// max_k_l (dp[30][27][k][l])
// 第i天的天气决定 i+1天能否移动
// 如:第0天天气决定第1天能否移动

// 先不考虑非矿山停留自愿停留情况
// for(short i=1;i<N;i++)
// {
// printf("第%d个点",i);
// for(auto j:mp[i])
// {
// printf("%d ",j);
// }
// printf("\n");
// }
// printf("???%d %d %d %d\n",xh_food[0],xh_food[2],xh_water[0],xh_water[1]);
for(short i=0;i<Day;i++)
{
printf("第%d天\n",i);
short tq=weather[i];
for(short j=1;j<=N;j++)
{
if(cz[j])// 村庄
{
for(short w=0;w<=405;w++)
{
for(short f=0;w*3+f*2<=1200;f++)
{
//购买或不够买物资(ww=0,ff=0就是不购买)
if(tq==2) //停留
{
short money=dp[i][j][w][f];
for(short ww=0;ww<=money/cost_water;ww++)
{
for(short ff=0;ff<=(FZ-(w+ww)*3)/2-f;ff++)
{

if(w+ww-xh_water[tq]>=0&&f+ff-xh_food[tq]>=0&&dp[i][j][w][f]-2*ww*cost_water-2*ff*cost_food>=0)
{
if(dp[i+1][j][w+ww-xh_water[tq]][f+ff-xh_food[tq]]<dp[i][j][w][f]-2*ww*cost_water-2*ff*cost_food)
{
dp[i+1][j][w+ww-xh_water[tq]][f+ff-xh_food[tq]]=dp[i][j][w][f]-2*ww*cost_water-2*ff*cost_food;
// path[i+1][j][w+ww-xh_water[tq]][f+ff-xh_food[tq]]={i,j,w,f,dp[i][j][w][f]-2*ww*cost_water-2*ff*cost_food};
path[i+1][j][w+ww-xh_water[tq]][f+ff-xh_food[tq]]={i,j,w,f};
}
}

}
}
}
else //从j走到jj
{
for(auto jj:g[j])
{
short money=dp[i][j][w][f];
for(short ww=0;ww<=money/cost_water;ww++)
{
for(short ff=0;ff<=(FZ-(w+ww)*3)/2-f;ff++)
{
if(w+ww-walk*xh_water[tq]>=0&&f+ff-walk*xh_food[tq]>=0&&dp[i][j][w][f]-buy*ww*cost_water-buy*ff*cost_food>=0)
{
if(dp[i+1][jj][w+ww-walk*xh_water[tq]][f+ff-walk*xh_food[tq]]<dp[i][j][w][f]-buy*ww*cost_water-buy*ff*cost_food)
{
dp[i+1][jj][w+ww-walk*xh_water[tq]][f+ff-walk*xh_food[tq]]=dp[i][j][w][f]-buy*ww*cost_water-buy*ff*cost_food;
// path[i+1][jj][w+ww-walk*xh_water[tq]][f+ff-walk*xh_food[tq]]={i,j,w,f,(short)dp[i][j][w][f]-buy*ww*cost_water-buy*ff*cost_food};
path[i+1][jj][w+ww-walk*xh_water[tq]][f+ff-walk*xh_food[tq]]={i,j,w,f};
}

}
}
}
}
}
}
}
}
else if (ks[j])// 矿山
{
for(short w=0;w<=405;w++)
{
for(short f=0;w*3+f*2<=1200;f++)
{
// 已经停留一天了,可以挖矿
if(w-dig*xh_water[tq]>=0&&f-dig*xh_food[tq]>=0)
{
if(dp[i+1][j][w-dig*xh_water[tq]][f-dig*xh_food[tq]]<dp[i][j][w][f]+1000&&dp[i][j][w][f]>=0)
{
dp[i+1][j][w-dig*xh_water[tq]][f-dig*xh_food[tq]]=dp[i][j][w][f]+1000;
// path[i+1][j][w-dig*xh_water[tq]][f-dig*xh_food[tq]]={i,j,w,f,(short)dp[i][j][w][f]+1000};
path[i+1][j][w-dig*xh_water[tq]][f-dig*xh_food[tq]]={i,j,w,f};
}

}
// 在矿山不挖矿或 不允许挖矿
if(tq==2) //停留但不挖矿
{
if(w-xh_water[tq]>=0&&f-xh_food[tq]>=0)
{
if(dp[i+1][j][w-xh_water[tq]][f-xh_food[tq]]<dp[i][j][w][f]&&dp[i][j][w][f]>=0)
{

dp[i+1][j][w-xh_water[tq]][f-xh_food[tq]]=dp[i][j][w][f];
// path[i+1][j][w-xh_water[tq]][f-xh_food[tq]]={i,j,w,f,dp[i][j][w][f]};
path[i+1][j][w-xh_water[tq]][f-xh_food[tq]]={i,j,w,f};
}

}
}
else
{
if(w-walk*xh_water[tq]>=0&&f-walk*xh_food[tq]>=0)
{
for(auto jj:g[j])
{
if(dp[i+1][jj][w-walk*xh_water[tq]][f-walk*xh_food[tq]]<dp[i][j][w][f]&&dp[i][j][w][f]>=0)
{
dp[i+1][jj][w-walk*xh_water[tq]][f-walk*xh_food[tq]]=dp[i][j][w][f];
// path[i+1][jj][w-walk*xh_water[tq]][f-walk*xh_food[tq]]={i,j,w,f,dp[i][j][w][f]};
path[i+1][jj][w-walk*xh_water[tq]][f-walk*xh_food[tq]]={i,j,w,f};
}

}
}
}
}
}
}
else //普通区
{
for(short w=0;w<=405;w++)
{
for(short f=0;w*3+f*2<=1200;f++)
{
if(tq==2) //在j点停留
{
if(w-xh_water[tq]>=0&&f-xh_food[tq]>=0&&dp[i][j][w][f]>=0)
{
if(dp[i+1][j][w-xh_water[tq]][f-xh_food[tq]]<dp[i][j][w][f])
{
dp[i+1][j][w-xh_water[tq]][f-xh_food[tq]]=dp[i][j][w][f];
// path[i+1][j][w-xh_water[tq]][f-xh_food[tq]]={i,j,w,f,dp[i][j][w][f]};
path[i+1][j][w-xh_water[tq]][f-xh_food[tq]]={i,j,w,f};
}
}
}
else// 走到jj点
{
for(auto jj:g[j])
{
if(w-walk*xh_water[tq]>=0&&f-walk*xh_food[tq]>=0&&dp[i][j][w][f]>=0)
{
if(dp[i+1][jj][w-walk*xh_water[tq]][f-walk*xh_food[tq]]<dp[i][j][w][f])
{

dp[i+1][jj][w-walk*xh_water[tq]][f-walk*xh_food[tq]]=dp[i][j][w][f];
// path[i+1][jj][w-walk*xh_water[tq]][f-walk*xh_food[tq]]={i,j,w,f,dp[i][j][w][f]};
path[i+1][jj][w-walk*xh_water[tq]][f-walk*xh_food[tq]]={i,j,w,f};

}

}
}
}
}
}
}
}
}
short ans=-inf;
node lastpath;
short last_water=0,last_food=0,last_day=Day;
for(short i=0;i<=Day;i++)
{
for(short w=0;w<=405;w++)
for(short f=0;w*3+2*f<=1200;f++)
{
if(dp[i][zd][w][f]>ans)
{
ans=dp[i][zd][w][f];
lastpath=path[i][zd][w][f];
last_water=w;
last_food=f;
last_day=char(i);
}
}
}
stack<node> s;
// freopen("outputQ2.txt","w",stdout);
printf("ans:%d\n",ans);
printf("day:%d weather:%d point:%d water:%d food:%d\n",last_day,weather[Day],zd,last_water,last_food);

node temppath=(node){last_day,zd,last_water,last_food};
s.push(temppath);

while(lastpath!=path[0][1][0][0])
{
s.push(lastpath);
printf("day:%d weather:%d point %d water:%d food:%d\n",lastpath.day,(int)weather[lastpath.day],(int)mp[lastpath.from],lastpath.water,lastpath.food);
temppath=lastpath;
lastpath=path[lastpath.day][lastpath.from][lastpath.water][lastpath.food];
}
}

结果

日期 所在区域 剩余资金数 剩余水量 剩余食物量
0 1 5300 130 405
1 2 5300 114 393
2 3 5300 98 381
3 4 5300 88 367
4 4 5300 78 357
5 12 5300 68 343
6 21 5300 52 331
7 21 5300 42 321
8 29 5300 32 307
9 30 5300 16 295
10 39 5300 0 283
11 39 5200 0 273
12 30 3410 163 261
13 30 4410 148 240
14 30 5410 124 222
15 30 6410 100 204
16 30 7410 76 186
17 30 8410 46 156
18 30 9410 16 126
19 39 9410 0 114
20 47 5730 180 188
21 55 5730 170 174
22 55 6730 155 153
23 55 7730 131 135
24 55 8730 116 114
25 55 9730 86 84
26 55 10730 62 66
27 55 11730 47 45
28 55 12730 32 24
29 56 12730 16 12
30 12 12730 0 0

末尾的哔哔

再优化

​ 后来和lms交流后发现自己村庄搜索代码写挫了,因为是递推的所以不用枚举购买的水和食物量,而是分别购买1箱水和1箱食物的状态转移。这样就能控制程序1s了。

难度

从oi来看的话我个人认为单纯dp应该有提高+难度?但是考虑到优化复杂度应该有黑题左右的难度了。我是有什么资格评价的哇

从ACM来看的话如果有时间限制的话应该是个银牌题吧,没有时间限制就是个铜牌题。本菜鸡做了大半天…