【蓝桥杯-0404（动态规划）】

/*
    f[i][j] 存的是走到 [i, j] 这个位置 一共有多少种方案
    f[i][j] = f[i - 1][j] + f[i][j - 1]
*/

#include 
#include 
#include 

using namespace std;

const int N = 40;

int f[N][N];

int main()
{
    int n, m;
    cin >> n >> m;
    
    for(int i = 1; i <= n; i ++ )
        for(int j = 1; j <= m; j ++ )
            if(i == 1 || j == 1) f[i][j] = 1;
    
    for(int i = 2; i <= n; i ++ )
        for(int j = 2; j <= m; j ++ )
        {
            if(i % 2 == 0 && j % 2 == 0) continue;
            
            f[i][j] = f[i - 1][j] + f[i][j - 1];
        }
        
    cout << f[n][m] << endl;
    return 0;
}

/*
    f[i][j] 表示 是否 可以用 <= i 个砝码 -> 得到 j 的重量;
    
    枚举每个物品, 同时枚举每个重量
    f[i][j] = f[i - 1][abs(j - w[i])] || f[i - 1][j + w[i]] || f[i-1][j]  
    
    结果: 看用总共 n 件一共可以有多少合法重量
*/

#include 
#include 
#include 
#define deb(x) cout << #x << "=" << x << endl
#define deb2(x, y) cout << #x << "=" << x << "," << #y << "=" << y << endl
#define deb3(x, y, z) cout << #x << "=" << x << "," << #y << "=" << y <<","<< #z << "=" << z << endl
#define deb4(x, y, z, w) cout << #x << "=" << x << "," << #y << "=" << y <<","<< #z << "=" << z << ","<< #w << "=" << w << endl
#define debv(v) for(auto x:v) cout<<x<<" "
#define gg exit(0);


using namespace std;

const int N = 101;

bool f[N][200000]; // 注意这个要设置到位
int w[N];

int main()
{
    int n;
    cin >> n;
    
    int sum = 0;
    for(int i = 1; i <= n; i ++ ) cin >> w[i], sum += w[i];
    
    f[0][0] = true;
    for(int i = 1; i <= n; i ++ )
        for(int j = 0; j <= sum; j ++ )
        {
            f[i][j] = f[i - 1][abs(j - w[i])] || f[i - 1][j + w[i]] || f[i - 1][j];
        }
    
    int res = 0;
    for(int i = 1; i <= sum; i ++ )
        if(f[n][i]) res ++ ;
            
    cout << res <<endl;
    
    return 0;
}

#include 
#include 
#include 
#define deb(x) cout << #x << "=" << x << endl
#define deb2(x, y) cout << #x << "=" << x << "," << #y << "=" << y << endl
#define deb3(x, y, z) cout << #x << "=" << x << "," << #y << "=" << y <<","<< #z << "=" << z << endl
#define deb4(x, y, z, w) cout << #x << "=" << x << "," << #y << "=" << y <<","<< #z << "=" << z << ","<< #w << "=" << w << endl
#define debv(v) for(auto x:v) cout<<x<<" "
#define gg exit(0);

using namespace std;
typedef unsigned long long ull;

ull N = 2021041820210418;

int cnt = 0;
ull prime[10000]; // , 这里越界了

int main()
{
    // 存入所有的因子
    for(int i = 1; i <= N / i; i ++ ) // 了, 不能除 0 
    {
        if(N % i == 0)
        {
            prime[cnt ++ ] = i;
            if(i * i != N) prime[cnt ++ ] = N / i;
        }
        
    }
    
   // debv(prime);
    
    // 遍历所有的 l, w, h;
    int res = 0;
    for(int l = 0; l < cnt; l ++ )
        for(int w = 0; w < cnt; w ++ )
            for(int h = 0; h < cnt; h ++ )
            {
                if(prime[l]*prime[w]*prime[h] == N) res ++ ;
            }
            
    cout << res <<endl;
    return 0;
}

#include 
#include 
#include 
#include 
#define deb(x) cout << #x << "=" << x << endl
#define deb2(x, y) cout << #x << "=" << x << "," << #y << "=" << y << endl
#define deb3(x, y, z) cout << #x << "=" << x << "," << #y << "=" << y <<","<< #z << "=" << z << endl
#define deb4(x, y, z, w) cout << #x << "=" << x << "," << #y << "=" << y <<","<< #z << "=" << z << ","<< #w << "=" << w << endl
#define debv(v) for(auto x:v) cout<<x<<" "
#define yes cout << 'Y' << 'E' << 'S' << endl
#define no cout << 'N' << 'O' << endl
#define gg exit(0);

using namespace std;

typedef pair<int,int> PII;

const int N = 11;


int n, m, Min = 1e9;
char g[N][N];
bool st[N][N];
int s[200];

void dfs(int x, int y, int step)
{
    if(x == n - 1 && y == m - 1)
    {
        s[step] ++ ;
        if(Min > step) Min = step;
        return ;
        
    }
    
    int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
    
    if(step > Min) return ; // 注意一定要剪枝, 最优性剪枝
    for(int i = 0; i < 4; i ++ )
    {
        int a = x + dx[i], b = y + dy[i];
        
        if(a < 0 || a >= n || b < 0 || b >= m) continue;
        if(st[a][b] || g[a][b] == '1') continue;
        
        st[a][b] = true;
        dfs(a, b, step + 1);
        st[a][b] = false;
    }

    return ;
}

int main()
{
    cin >> n >> m;
    
    for(int i = 0; i < n; i ++ )
        for(int j = 0; j < m; j ++ )
            cin >> g[i][j];
            
    
    dfs(0, 0, 0);
    
    cout << s[Min];
    

    return 0;
}

#include 
#include 
#include 
#define x first
#define y second
#define deb(x) cout << #x << "=" << x << endl
#define deb2(x, y) cout << #x << "=" << x << "," << #y << "=" << y << endl
#define deb3(x, y, z) cout << #x << "=" << x << "," << #y << "=" << y <<","<< #z << "=" << z << endl
#define deb4(x, y, z, w) cout << #x << "=" << x << "," << #y << "=" << y <<","<< #z << "=" << z << ","<< #w << "=" << w << endl
#define debv(v) for(auto x:v) cout<<x<<" "
#define yes cout << 'Y' << 'E' << 'S' << endl
#define no cout << 'N' << 'O' << endl
#define gg exit(0);


using namespace std;
typedef pair<int, int> PII;

const int N = 1e3 + 10, M = N * N;

int n, m;
char g[N][N];
bool st[N][N]; // 看看是否能遍历到 [n, m] 这个点
PII q[M];

string bfs()
{
    // 初始化
    st[0][0] = true;
    q[0] = {0, 0};
    int hh = 0, tt = 0;
    
    // 具象化
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
    while(hh <= tt)
    {
        PII t = q[hh ++ ];
        for(int i = 0; i < 4; i ++ )
        {
            int a = t.x + dx[i], b = t.y + dy[i];
            if(a < 0 || a >= n || b < 0 || b >= m ) continue;
            if(g[a][b] == '1' || st[a][b]) continue;
            
            st[a][b] = true;
            q[++ tt] = {a, b};
        }
        
    }
    
    if(st[n - 1][m - 1] == 1) return "Yes";
    else return "No";
}
 
int main()
{
    //int n, m; emmm, 全局变量和局部变量, 之后还是不要开局部吧
    cin >> n >> m;
    for(int i = 0; i < n; i ++ ) cin >> g[i];
    
    cout << bfs();
}

/*
    f[i]: 以 a[i] 结尾的最长上升子序列有多少
    
    计算: f[i] = f[j] + 1;
    
    结果: 以 a[i] 结尾的最长上升子序列
*/

#include 
#include 
#include 
#define deb(x) cout << #x << "=" << x << endl
#define deb2(x, y) cout << #x << "=" << x << "," << #y << "=" << y << endl
#define deb3(x, y, z) cout << #x << "=" << x << "," << #y << "=" << y <<","<< #z << "=" << z << endl
#define deb4(x, y, z, w) cout << #x << "=" << x << "," << #y << "=" << y <<","<< #z << "=" << z << ","<< #w << "=" << w << endl
#define debv(v) for(auto x:v) cout<<x<<" "
#define yes cout << 'Y' << 'E' << 'S' << endl
#define no cout << 'N' << 'O' << endl
#define gg exit(0);

using namespace std;

const int N = 2010;

int n;
int a[N], f[N];

int main()
{
    cin >> n;
    
    for(int i = 0; i < n; i ++ ) cin >> a[i];
    
    for(int i = 0; i < n; i ++ )
    {
        f[i] = 1;
        for(int j = 0; j < i; j ++ )
            if(a[j] < a[i]) f[i] = max(f[i], f[j] + 1);
        
    }
    
    int res = 0;
    for(int i = 0; i < n; i ++ ) // 注意结尾是这个
        res = max(res, f[i]);
        
    cout << res;
    return 0;
}

// 1, 状态定义: f[i][j] -> 以 a[i][j] 结尾的 最大的数量
// 2, 状态属性: MAX

// 3, 状态计算: max(f[i - 1][j], f[i][j - 1]) + w[i][j];

#include 
#include 

using namespace std;

const int N = 110;

int n, m;
int f[N][N];
int g[N][N];

int main()
{
    int T;
    cin >> T;

    while(T -- )
    {
        cin >> n >> m;

        for(int i = 1; i <= n; i ++ )
            for(int j = 1; j <= m; j ++ )
                cin >> g[i][j];

        for(int i = 1; i <= n; i ++ )
            for(int j = 1; j <= m; j ++ )
                f[i][j] = max(f[i - 1][j], f[i][j - 1]) + g[i][j];


        printf("%d\n", f[n][m]);
    }
}

// f[i][j] 的定义为: 当前所有的能够到达该地方的路径的最小值 (排0)

#include 
#include 
#include 

using namespace std;

typedef pair<int, int> PII;

const int INF = 0x3f3f3f3f;
const int N = 110;

int n;
int g[N][N];
int f[N][N];

int main()
{
    cin >> n;

    for(int i = 1; i <= n; i ++ )
        for(int j = 1; j <= n; j ++ )
            cin >> g[i][j];

    for(int i = 1; i <= n; i ++ )
        for(int j = 1; j <= n; j ++ )
        {
            if(i == 1 && j == 1) f[i][j] = g[i][j];
            else
            {
                f[i][j] = INF;
                if(i > 1) f[i][j] = f[i - 1][j] + g[i][j];
                if(j > 1) f[i][j] = min(f[i][j], f[i][j - 1] + g[i][j]);

            }
        }

    cout << f[n][n] << endl;

    return 0;
}