【数模】2020B 穿越沙漠

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

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

穿越沙漠

题意

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

游戏的基本规则如下：

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

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

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

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

（5）玩家在原地停留一天消耗的资源数量称为基础消耗量，行走一天消耗的资源数量为基础消耗量的2倍。

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

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

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

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

• 关卡 1
• 关卡 2

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

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

思路

很明显的一个动态规划

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

$$ans=max_{w,f,i} \quad dp[k][zd][w][f]$$

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

初始值设定

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

$$dp[0][qd][w][f]=10000-cost\_water*w-cost\_food*f \quad w \in [0,400] f\in [0,600]$$

其中$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+1][jj][w-walk*xh_water[tq]][f-walk*xh_food[tq]]=max(dp[k][j][w][f])

优化

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

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

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

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

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

化简之后的路径图如下：

​ 可见有效点只有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来看的话如果有时间限制的话应该是个银牌题吧，没有时间限制就是个铜牌题。本菜鸡做了大半天…