妈妈省的0_o

常规
1

上dp cpu糊了
上课听蒙，做题干瞪
有没有大佬发一下有关dp动规的笔记啊XD（脑子不好见谅）
附赠个好van的铀锡（ 感谢！
Note.ms

2 个赞
2 
#include <iostream>
#include <conio.h>
#include <windows.h>

using namespace std;
const int width = 20;  // 游戏区域宽度
const int height = 20; // 游戏区域高度
int x, y;             // 蛇头的坐标
int fruitX, fruitY;   // 食物的坐标
int score;            // 分数
int tailX[100], tailY[100]; // 蛇的身体坐标
int tailLength;       // 蛇的长度
enum eDirection { STOP = 0, LEFT, RIGHT, UP, DOWN }; // 蛇的方向
eDirection dir;
bool gameOver;        // 游戏结束标志
void Setup() {
    gameOver = false;
    dir = STOP;
    x = width / 2;
    y = height / 2;
    fruitX = rand() % width;
    fruitY = rand() % height;
    score = 0;
}
void Draw() {
    system("cls"); // 清空上一个帧
    for (int i = 0; i < width + 2; i++)
        cout << "#";
    cout << endl;

    for (int i = 0; i < height; i++) {
        for (int j = 0; j < width; j++) {
            if (j == 0)
                cout << "#";

            if (i == y && j == x) // 绘制蛇头
                cout << "O";
            else if (i == fruitY && j == fruitX) // 绘制食物
                cout << "F";
            else {
                bool printTail = false;
                for (int k = 0; k < tailLength; k++) {
                    if (tailX[k] == j && tailY[k] == i) {
                        cout << "o"; // 绘制蛇身体
                        printTail = true;
                    }
                }
                if (!printTail)
                    cout << " ";
            }

            if (j == width - 1)
                cout << "#";
        }
        cout << endl;
    }

    for (int i = 0; i < width + 2; i++)
        cout << "#";
    cout << endl;

    cout << "Score:" << score << endl; // 显示当前分数
}
void Input() {
    if (_kbhit()) { // 使用conio.h库函数_kbhit判断是否有按键输入
        switch (_getch()) { // 使用conio.h库函数_getch获取按键输入
        case 'a':
            dir = LEFT;
            break;

        case 'd':
            dir = RIGHT;
            break;

        case 'w':
            dir = UP;
            break;

        case 's':
            dir = DOWN;
            break;

        case 'x':
            gameOver = true;
            break;
        }
    }
}
void Logic() {
    int prevX = tailX[0];
    int prevY = tailY[0];
    int prev2X, prev2Y;
    tailX[0] = x;
    tailY[0] = y;
    for (int i = 1; i < tailLength; i++) {
        prev2X = tailX[i];
        prev2Y = tailY[i];
        tailX[i] = prevX;
        tailY[i] = prevY;
        prevX = prev2X;
        prevY = prev2Y;
    }

    switch (dir) { // 根据方向更新蛇头的坐标
    case LEFT:
        x--;
        break;

    case RIGHT:
        x++;
        break;

    case UP:
        y--;
        break;

    case DOWN:
        y++;
        break;
    }

    if (x >= width) x = 0; else if (x < 0) x = width - 1; // 如果蛇出界，从另一侧出来
    if (y >= height) y = 0; else if (y < 0) y = height - 1;

    for (int i = 0; i < tailLength; i++) {
        if (tailX[i] == x && tailY[i] == y) // 撞到身体，游戏结束
            gameOver = true;
    }

    if (x == fruitX && y == fruitY) { // 吃到食物，分数加一，增加蛇长度，重新生成食物
        score += 10;
        fruitX = rand() % width;
        fruitY = rand() % height;
        tailLength++;
    }
}
int main() {
    Setup();
    while (!gameOver) {
        Draw();
        Input();
        Logic();
        Sleep(10); // 控制游戏帧率
    }
    return 0;
}
2 个赞
3

note容易被删

2 个赞
4

az

2 个赞
5

本质上就是把每个位置的解都存起来方便下次用，舍空间求时间。能用动态规划解决的问题，需要满足三个条件：最优子结构，无后效性和子问题重叠。

再具体点的话，包含万物之 dp 动态规划的东西实在是有点多，不太了解问的是哪一种 :sweat_drops:

如果你想了解具体的话相关知识的话，可以看下 OI Wiki 的资料。

2 个赞
6

感谢大佬！
争取去理解 :melting_face:

2 个赞