整体思路

• 最重要的目标是能够通过沙漠，在确保这个问题能够完成的基础上才是要获取更多资金。因此我们在做每一步决策时要首先判断当前还能否维持走到终点。这个信息是能够预处理的，注意这个信息和时间有关，那么我们要维护从某个点某天开始能在规定时间内走到终点的最小食物需求量和最小水需求量。因为时间轴的有序性，所以可以dp来做。
• 按照以上思路维护的话，村庄的问题无法解决，那么我们需要再加一个资金维度。 由于我们在问题1中资金量不会超过25000， 且只会是5的倍数，所以资金有5000个状态， 总共大概不到一千万个状态数。转移也很简单。这样大概能够解决前两关， 对于后面的关卡，看限制条件还是有些意思的，估计不能得到精确解，而是想一些贪心方式，然后枚举天气情况验证一下。
• 第二题能给一种方案给出一个评价标准， 然后第三题也许能套用

第一、二关

• 如上

第三关

• 高温和沙暴天气挖矿都是亏的， 晴朗天气也只能赚35元。
• 好消息是没有村庄也没有沙暴， 天气状态一共$2^10$种， 容易枚举后利用不同评判标准评价我们的方案。
• 路线图也很好规划， 不挖矿的话四天的路程， 挖矿的话五天的路程。
• 现在的决策影响问题主要有2， 第一个是天气不好的时候是否应当等着， 第二个是如何应对挖矿。
• 这两个问题我猜都能通过枚举天气选择期望最小的来解决， 问题是我们并不是要求期望最小， 我们首先要保证的是能够通过沙漠。 所以我们先量化一个指标x， 对于在所有天气情况下通过的几率至少占x%的方法

第四关

• 天气30天就不能枚举了， 这里不知道要进行怎么假设。希望能采用贪心的方法， 每一步进行一个估价函数， 然后决定下一步的移动。很显然这个需要我们天气情况做支持， 我倾向于直接假设天气的概率，然后决策的时候好转移， 然后我们可以作图展示当我们有不同概率假设的时候， 他都能取得较好结果。

第五关

• 这个更像第一关的限制， 我不太了解题意是什么
• 如果说每个人只是单独要求自己获利最高， 他俩甚至能合作，
• 如果说不是这样的话， 争名次的话，题目又不一样了。我倾向于还是自己获利最高。
• 可以看到的是， 多人走一条路不划算， 等价的路太多可以分着走。 是不是说明只需要考虑是否一起挖矿， 是否一起补给。 一起挖矿是亏的， 所以绝对不会一起挖矿。
• 因为他俩的路径是实现决定的， 那么就可以假定对面怎么走， 取自己期望收益最高的那条。

第六关

• 感觉像是第四关， 不过贪心计算需要考虑更多， 不会估价 寄了

动态规划代码

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

int initialFoud, income, maxWeight, maxDate, waterWeight, foodWeight, waterPrice, foodPrice, sunnyFoodCost, sunnyWaterCost, highTemperatureFoodCost, highTemperatureWaterCost, sandstormFoodCost, sandstormWaterCost, maxPoint;
// 题目中的初始资金、基础收益、背包容量、天数、单位水重量、单位食物重量、水价格、食物价格、三种天气下的不同消耗, 点个数。
int weather[31] = {0, 2, 2, 1, 3, 1, 2, 3, 1, 2, 2, 3, 2, 1, 2, 2, 2, 3, 3, 2, 2, 1, 1, 2, 1, 3, 2, 1, 1, 2, 2};
vector<int> to[101];
//存图的边

struct FourValueNode{ //空间不够， 用来存路径
    int a, b, c, d;
    FourValueNode(int x, int xx, int xxx, int xxxx)
    {
        a = x;
        b = xx;
        c = xxx;
        d = xxxx;
    }
    bool operator < (const FourValueNode &tmp) const {
        if(a == tmp.a && b == tmp.b && c == tmp.c) return d < tmp.d;
        if(a == tmp.a && b == tmp.b) return c < tmp.c;
        if(a == tmp.a) return b < tmp.b;
        return a < tmp.a;
    }
};

int f[2][65][601][401], tmp[601][401];;
map<FourValueNode, int> path;
// 这里记录路径， 但是记录的是上一步进行了什么操作 编码为 97 - > 停止，  1 ~ maxPoint - > 行走， 99 - > 挖矿， 98->终点不动->, Qxxxyyy 购物， 表示行动是Q分别买了xxx和yyy个

int noteFood[101], noteWater[101], noteMoney[101], notePlace[101]; 
// 用来记录获取答案， 记录最有解下每天状态

struct Point{
    int id;
    bool isVillage;
    bool isMine;
}point[101];

void Push(int vi, int vj) // 加边
{
    to[vi].push_back(vj);
    to[vj].push_back(vi);
}


void Initalize(int number) // 各种参数以及图上信息的初始化。
{
    initialFoud = 10000;
    maxWeight = 1200;
    maxDate = 30;
    waterWeight = 3;
    foodWeight = 2;
    waterPrice = 5;
    foodPrice = 10;
    income = 1000;
    maxPoint = 27;
    sunnyFoodCost = 7;
    sunnyWaterCost = 5;
    highTemperatureFoodCost = 6;
    highTemperatureWaterCost = 8;
    sandstormFoodCost = 10;
    sandstormWaterCost = 10;
    if(number == 1){
        maxPoint = 27;
        point[15].isVillage = true;
        point[12].isMine = true;
        Push(1, 25);
        Push(1, 2);
        Push(2, 3);
        Push(3, 25);
        Push(3, 4);
        Push(4, 5);
        Push(4, 24);
        Push(4, 25);
        Push(5, 6);
        Push(5, 24);
        Push(6, 7);
        Push(6, 23);
        Push(6, 24);
        Push(7, 8);
        Push(7, 22);
        Push(8, 9);
        Push(8, 22);
        Push(9, 10);
        Push(9, 15);
        Push(9, 16);
        Push(9, 17);
        Push(9, 21);
        Push(9, 22);
        Push(10, 11);
        Push(10, 15);
        Push(10, 13);
        Push(11, 12);
        Push(11, 13);
        Push(12, 13);
        Push(12, 14);
        Push(13, 14);
        Push(13, 15);
        Push(14, 15);
        Push(14, 16);
        Push(15, 16);
        Push(16, 17);
        Push(16, 18);
        Push(17, 18);
        Push(17, 21);
        Push(18, 19);
        Push(18, 20);
        Push(19, 20);
        Push(20, 21);
        Push(21, 23);
        Push(21, 22);
        Push(21, 27);
        Push(22, 23);
        Push(23, 24);
        Push(23, 26);
        Push(24, 25);
        Push(24, 26);
        Push(25, 26);
        Push(26, 27);
    }
    else{
        maxPoint = 64;
        point[30].isMine = true;
        point[55].isMine = true;
        point[39].isVillage = true;
        point[62].isVillage = true;
        for(int i = 1; i <= 64; i++)
        {
            if(i % 8 != 0) Push(i, i + 1);
        }
        for(int i = 1; i <= 56; i++)
        {
            Push(i, i + 8);
            if((((i - 1) / 8) & 1) && (i % 16 != 0)) Push(i, i + 9);
            if((((i - 1) / 8) & 1) == 0 && (i % 16 != 1)) Push(i, i + 7);
        }
    }
}


int main()
{
    freopen("input.txt", "r", stdin);//freopen("output.txt", "w", stdout);
    int number;
    //关卡序号
    cin >> number;
    Initalize(number);
    memset(f, -1, sizeof(f));
    int now = 1, last = 0; //循环数组
    for(int i = 0; i <= maxWeight / foodWeight; i++)
    {
        for(int j = 0; j <= maxWeight / waterWeight; j++)
        {
            if(i * foodWeight + j * waterWeight > maxWeight) break;
            if(i * foodPrice + j * waterPrice > initialFoud) break;
            f[now][1][i][j] = initialFoud - i * foodPrice - j * waterPrice;
        }
    }

    for(int tim = 1; tim <= maxDate; tim++)
    {
        cout << tim << "\n";
        swap(now, last);
        memset(f[now], -1, sizeof(f[now]));
        for(int i = 1; i <= maxPoint; i++)
        {
            for(int j = 0; j <= maxWeight / foodWeight; j++)
            {
                for(int k = 0; k <= maxWeight / waterWeight; k++)
                {
                    if(f[last][i][j][k] == -1) continue;                    
                    int baseFoodCost, baseWaterCost;
                    if(weather[tim] == 1) baseFoodCost = sunnyFoodCost, baseWaterCost = sunnyWaterCost;
                    if(weather[tim] == 2) baseFoodCost = highTemperatureFoodCost, baseWaterCost = highTemperatureWaterCost;
                    if(weather[tim] == 3) baseFoodCost = sandstormFoodCost, baseWaterCost = sandstormWaterCost;
                    //决策分为 停止， 移动， 挖矿， 购物, 已经到终点了
                    /******************** 停止  **************************/
                    if(j >= baseFoodCost && k >= baseWaterCost && f[now][i][j - baseFoodCost][k - baseWaterCost] < f[last][i][j][k])
                    {
                        f[now][i][j - baseFoodCost][k - baseWaterCost] = f[last][i][j][k];
                        path[FourValueNode(tim, i, j - baseFoodCost, k - baseWaterCost)] = 97;
                    }
                    /******************** 移动  **************************/
                    if(weather[tim] != 3 && j >= baseFoodCost * 2 && k >= baseWaterCost * 2)
                    {
                        for(int l = 0; l < to[i].size(); l++)
                        {
                            int vj = to[i][l];
                            if(f[now][vj][j - baseFoodCost * 2][k - baseWaterCost * 2] < f[last][i][j][k])
                            {
                                f[now][vj][j - baseFoodCost * 2][k - baseWaterCost * 2] = f[last][i][j][k];
                                path[FourValueNode(tim, vj, j - baseFoodCost * 2, k - baseWaterCost * 2)] = i;
                            }
                        }
                    }
                    /******************** 挖矿  **************************/
                    if(point[i].isMine && j >= baseFoodCost * 3 && k >= baseWaterCost * 3 && f[now][i][j - baseFoodCost * 3][k - baseWaterCost * 3] < f[last][i][j][k] + income){
                        f[now][i][j - 3 * baseFoodCost][k - 3 * baseWaterCost] = f[last][i][j][k] + income;
                        path[FourValueNode(tim, i, j - baseFoodCost * 3, k - baseWaterCost * 3)] = 99;
                    }
                    
                    /******************** 到终点了 **************************/
                    if(i == maxPoint && j == 0 && k == 0)
                    {
                        if(f[now][i][j][k] < f[last][i][j][k])
                        {
                            f[now][i][j][k] = f[last][i][j][k];
                            path[FourValueNode(tim, i, j, k)] = 98;
                        }
                    }
                }
            }
            /*************************购物的背包********************/
            if(!point[i].isVillage) continue; 
            memset(tmp, -1, sizeof(tmp));
            for(int j = 0; j <= maxWeight / foodWeight; j++)
            {
                for(int k = 0; k <= maxWeight / waterWeight; k++)
                {
                    if(f[now][i][j][k] == -1) continue;                    
                    for(int l = (maxWeight - j * foodWeight - k * waterWeight) / foodWeight; l >= 0; l--)
                    {
                        for(int r = (maxWeight - j * foodWeight - k * waterWeight) / waterWeight; r >= 0; r--)
                         {
                                if(j * foodWeight + k * waterWeight + l * foodWeight + r * waterWeight > maxWeight) continue;
                                if(l * foodPrice + r * waterPrice > f[now][i][j][k]) continue;
                                if(f[now][i][j + l][k + r] < f[now][i][j][k] - l * foodPrice * 2 - r * waterPrice * 2)
                                {
                                    f[now][i][j + l][k + r] = f[now][i][j][k] - l * foodPrice * 2 - r * waterPrice * 2;
                                    tmp[j + l][k + r] =  path[FourValueNode(tim, i, j, k)] * 1000000 + l * 1000 + r;
                                } 
                        }
                    }
                }
            }
            for(int j = 0; j <= maxWeight / foodWeight; j++)
            {
                for(int k = 0; k <= maxWeight / waterWeight; k++)
                {
                    if(tmp[j][k] == -1) continue;                    
                    path[FourValueNode(tim, i, j, k)] = tmp[j][k];
                }
            }
        }
    }

    int maxans = -1;

    for(int j = 0; j <= maxWeight / foodWeight; j++)
    {
        for(int k = 0; k <= maxWeight / waterWeight; k++)
        {
            if(f[now][maxPoint][j][k] > maxans)
            {
                maxans = f[now][maxPoint][j][k];
                notePlace[maxDate + 1] = maxPoint;
                noteFood[maxDate + 1] = j;
                noteWater[maxDate + 1] = k;
                noteMoney[maxDate + 1] = f[now][maxPoint][j][k];
            }
        }
    }
    
    for(int i = maxDate; i >= 1; i--)
    {
        int baseFoodCost, baseWaterCost;
        if(weather[i] == 1) baseFoodCost = sunnyFoodCost, baseWaterCost = sunnyWaterCost;
        if(weather[i] == 2) baseFoodCost = highTemperatureFoodCost, baseWaterCost = highTemperatureWaterCost;
        if(weather[i] == 3) baseFoodCost = sandstormFoodCost, baseWaterCost = sandstormWaterCost;
        int getPath = path[FourValueNode(i, notePlace[i + 1], noteFood[i + 1], noteWater[i + 1])];
        if(getPath == 99)
        {
            notePlace[i] = notePlace[i + 1];
            noteFood[i] = noteFood[i + 1] + baseFoodCost * 3;
            noteWater[i] = noteWater[i + 1] + baseWaterCost * 3;
            noteMoney[i] = noteMoney[i + 1] - income;
        }
        else if(getPath == 97)
        {
            notePlace[i] = notePlace[i + 1];
            noteFood[i] = noteFood[i + 1] + baseFoodCost;
            noteWater[i] = noteWater[i + 1] + baseWaterCost;
            noteMoney[i] = noteMoney[i + 1];
        }
        else if(getPath <= maxPoint)
        {
            notePlace[i] = getPath;
            noteFood[i] = noteFood[i + 1] + baseFoodCost * 2;
            noteWater[i] = noteWater[i + 1] + baseWaterCost * 2;
            noteMoney[i] = noteMoney[i + 1];
        }
        else if(getPath != 98) {
            int x = getPath / 1000000;
            if(x == 97)
            {
                notePlace[i] = notePlace[i + 1];
                noteFood[i] = noteFood[i + 1] + baseFoodCost - (getPath % 1000000) / 1000;
                noteWater[i] = noteWater[i + 1] + baseWaterCost - getPath % 1000;
                noteMoney[i] = noteMoney[i + 1] + (getPath % 1000000) / 1000 * foodPrice * 2 + getPath % 1000 * waterPrice * 2;
            }
            else {
                notePlace[i] = x;
                noteFood[i] = noteFood[i + 1] + baseFoodCost * 2 - (getPath % 1000000) / 1000;
                noteWater[i] = noteWater[i + 1] + baseWaterCost * 2 - getPath % 1000;
                noteMoney[i] = noteMoney[i + 1] + (getPath % 1000000) / 1000 * foodPrice * 2 + getPath % 1000 * waterPrice * 2;
            }
        }
        else{
            notePlace[i] = notePlace[i + 1];
            noteFood[i] = noteFood[i + 1];
            noteWater[i] = noteWater[i + 1];
            noteMoney[i] = noteMoney[i + 1];
        }
    }
    for(int i = 1; i <= maxDate + 1; i++)
    {
        cout << notePlace[i] << " " << noteMoney[i] << " " << noteWater[i] << " " << noteFood[i] << "\n"; 
    }
    return 0;
}