题目描述

耗子哥最近迷上了下象棋，但是他在下一种另类的象棋，他将棋子倒在了棋盘上，其中只有一个黑卒，他想尝试能不能用这个黑卒，在不更改其他棋子位置，不吃其他棋子，也不能从其他棋子上飞过的情况下，吃到红方的将棋。
象棋的棋盘大小为9*10共90个位置可以放棋子，棋子数量不限，黑卒的位置和红将的位置会标注出来。

输入描述:

输入包含9列10行数字，其中0表示上面没有棋子，1表示上面有其他棋子，2表示上面放的棋子是黑卒，3表示上面棋子是红将，题目保证一盘棋中只有一个黑卒和一个红将。

输出描述:

如果能够吃到红将，则输出yes，否则输出no。

样例输入

200000000
000000000
000000000
000000000
000000000
000000000
000000000
000000000
000000000
000000003

输出

yes

样例输入

200000000
000000000
000000000
000010000
000131000
000010000
000000000
000000000
000000000
000000000

输出

no

C++ 代码

#include <iostream>
#include <cstring>

using namespace std;
const int N =  11;
char a[N][N];
bool b[N][N];
int r1,l1,r2,l2;
void dfs(int x,int y)
{
    if(x < 1 || x > 10 || y < 1 || y > 9 || b[x][y] == true) return ;
    if(a[x][y] != '1') b[x][y] = true;
    if(b[x][y] == true)
    {
        dfs(x + 1,y);
        dfs(x - 1,y);
        dfs(x,y + 1);
        dfs(x,y - 1);
    }

}
int main()
{
    for(int i = 1;i <= 10;i ++)
        for(int j = 1;j <= 9;j ++) 
            cin >> a[i][j];

    memset(b,false,sizeof b);
    for(int i = 1;i <= 10;i ++)
        for(int j = 1;j <= 9;j ++)
        {
            if(a[i][j] == '2') r1 = i,l1 = j;
                if(a[i][j] == '3') r2 = i,l2 = j;
        }
    dfs(r1,l1);
    if(b[r2][l2] == true) cout << "yes";
    else cout << "no";
    return 0;
}

C++ 代码

//难得还是怎么划分集合，以及状态计算
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1010;
int n;
long long a[N],f[N],res = 0;//f[i]表示从第一个数字开始算，以a[i]结尾的最大的上升序列
int main()
{
    cin >> n;
    for(int i = 1;i <= n;i ++)  cin >> a[i];

    for(int i = 1;i <= n;i ++)
    {
        f[i] = 1;
        for(int j = 1;j < i;j ++)
        {
            if(a[i] > a[j]) f[i] = max(f[i],f[j] + 1);//如果a[i]大于a[j],说明其满足递增序列，
            //则f[i]的单调递增序列位f[j] + 1.因为f[j]里存的
            //是从第一个数字开始到j的最大上升序列，a[j]最大,所以应为f[j] + 1，1指的是a[j]这个数
        }
        res = max(res,f[i]);
    }
    cout << res;
    return 0;
}

从最后一步往前想，就可以得到了，应该算是对DP的初步理解

#include <iostream>

using namespace std;
const int N = 110;
int n,r,c;//n几亩花生田,r行数,c列数
int a[N][N],d[N][N];//花生田每个位置有多少花生
int main()
{
    cin >> n;
    for(int i = 0;i < n;i ++)
    {
        cin >> r >> c;
        for(int j = 1;j <= r;j ++)
            for(int k = 1;k <= c;k ++)
                cin >> a[j][k];
        for(int j = 1;j <= r;j ++)
            for(int k = 1;k <= c;k ++)
                    d[j][k] = max(a[j][k] + d[j - 1][k],a[j][k] + d[j][k - 1]);
        cout << d[r][c] << endl;    
    }
}

DP

#include <iostream>

using namespace std;
const int N = 110;
int n,r,c;//n几亩花生田,r行数,c列数
int d[N][N];//花生田每个位置有多少花生
int main()
{
    cin >> n;
    for(int i = 0;i < n;i ++)
    {
        cin >> r >> c;
        for(int j = 1;j <= r;j ++)
            for(int k = 1;k <= c;k ++)
                cin >> d[j][k];
        for(int j = 1;j <= r;j ++)
            for(int k = 1;k <= c;k ++)
                d[j][k] = max(d[j - 1][k],d[j][k - 1]) + d[j][k];
        cout << d[r][c] << endl;    
    }
}

DP优化(其实么看出哪里优化了 -QAQ-)，主要是与1进行&运算时，先换成2进制，看个位

#include <iostream>
#include <cstring>
using namespace std;
const int N = 110;
int n,m;
int a[N][N];
int f[2][N];
int main ()
{
    int T;
    cin >> T;
    while (T--) 
    {
        memset (f,0,sizeof (f));
        cin >> n >> m;
        for (int i = 1;i <= n;i++)
            for (int j = 1;j <= m;j++) 
                cin >> a[i][j];
        for (int i = 1;i <= n;i++)
        {
            for (int j = 1;j <= m;j++) f[i & 1][j] = max (f[(i - 1) & 1][j],f[i & 1][j - 1]) + a[i][j];
            //共两位，如果二进制个位是1则，该位的结果存在第二行，否则存在第一行
        }
        cout << f[n & 1][m] << endl;
    }
    return 0;
}

#include <iostream>

using namespace std;
const int N = 1010;
int n,r,c;//n几亩花生田,r行数,c列数
int a[N][N],d[N][N];
//数组a表示花生田每个位置有多少花生,数组d表示花生田从起点走到每个位置最多可以获得多少花生
int dx[4] = {-1,0,1,0},dy[4] = {0,-1,0,1};
int main()
{
    cin >> n;
    for(int i = 0;i < n;i ++)
    {
        cin >> r >> c;
        for(int j = 1;j <= r;j ++)
            for(int k = 1;k <= c;k ++)
                cin >> a[j][k];
        for(int j = 1;j <= r;j ++)
            for(int k = 1;k <= c;k ++)
                for(int i = 0;i < 4;i ++)
                {
                    d[j][k] = max(a[j][k] + d[j - 1][k],a[j][k] + d[j][k - 1]);
                }
        cout << d[r][c] << endl;    
    }
}

C++ 代码

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int n,m;
int v[N],w[N];
int f[N][N];//f[i][j], j体积下前i个物品的最大价值 
int main()
{
    cin >> n >> m;
    for(int i = 1;i <= n;i ++) cin >> v[i] >> w[i];//物品的体积是 v，价值是 w
    for(int i = 1;i <= n;i ++)//对每个物品进行选择
    {
        for(int j = 1;j <= m;j ++)
        if(v[i] > j)//第i个物品不选
        {
            f[i][j] = f[i - 1][j];
        }
        else//选
        {
            f[i][j] = max(f[i - 1][j - v[i]] + w[i], f[i - 1][j]);
        }
    }
    cout << f[n][m];
    return 0;
}

//二维模拟
  \i     1 2 3 4 5
j 

1        2 2 2 2 2

2        2 3 6 6 6

3        2 3 6 6 8

4        2 3 6 6 8

C++ 代码

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int n,m;
int v[N],w[N];
int f[N];//N件物品，背包容量j下的最优解。
//改成一维滚动数组，可以将f优化为一维
int main()
{
    cin >> n >> m;
    for(int i = 1;i <= n;i ++) cin >> v[i] >> w[i];//物品的体积是 v，价值是 w
    for(int i = 1;i <= n;i ++)//对每个物品进行选择
    {
        for(int j = m;j >= 1;j --)//若优化为一维数组后，若正序输出，则不等价与f[j - v[i]]
        //因为f[i - 1][j - v[i]]是上一行的，改后因为f[j - v[i]]小于f[j]所以被更新成了这一行的
        //倒叙输出后，即可让同一行的f[j - v[i]]在f[j]之后被更新
        {
            if(v[i] > j) f[j] = f[j];
            else
            f[j] = max(f[j],f[j - v[i]] + w[i]);
            //f[i][j] = max(f[i - 1][j],f[i - 1][j - v[i]] + w[i]) 
        }

    }
    cout << f[m];
    return 0;
}

再将不必要的去掉即可得到优化的代码

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int n,m;
int v[N],w[N];
int f[N];//N件物品，背包容量j下的最优解。
//改成一维滚动数组，可以将f优化为一维
int main()
{
    cin >> n >> m;
    for(int i = 1;i <= n;i ++) cin >> v[i] >> w[i];//物品的体积是 v，价值是 w
    for(int i = 1;i <= n;i ++)//对每个物品进行选择
    {
        for(int j = m;j >= v[i];j --)
            f[j] = max(f[j],f[j - v[i]] + w[i]);
    }
    cout << f[m];
    return 0;
}

#include <iostream>

using namespace std;
int n,res,cnt;
int main()
{
    cin >> n;
    res = n;
    if(n < 3)
    {
        cout << n;
        return 0;
    }
    while(n / 3 >= 1)
    {   cnt = n % 3;
        n = n / 3;//换了这么多
        res += n;
        n = n + cnt;
    }
    cout << res;
}

#include <iostream>
#include <algorithm>

using namespace std;
const int N = 100;
int n;
int a[N],b[N];
int main()
{
    cin >> n;
    for(int i = 0;i < n;i ++) cin >> a[i];
    int l = 0,r = 0;
    for(int i = 0;i < n;i ++)
    {
        if(abs(a[0]) > abs(a[i]) && a[i] > 0 ) l ++;
        else if(abs(a[0]) < abs(a[i]) && a[i] < 0) r ++;
    }
    if((a[0] > 0 && r == 0) || (a[0] < 0 && l == 0)) cout << 1;
    else cout << l + r + 1;//本来就有一只感染的，所以要加1
    return 0;
}

#include <iostream>

using namespace std;

int main()
{
    int n,m;
    cin >> n >> m;
    cout << ((n - 1) * (m - 1) - 1);
    return 0;
}

C++ 代码

//暴力枚举，只过了5个样例，没想到怎么优化
#include <iostream>

using namespace std;
const int N = 1000;//没想到N可以取那么大 QAQ
bool st[N];
int main()
{
    int n,m;
    cin >> n >> m;
    int res = min(n,m) - 1;
    for(int i = res;i <= N;i ++)
    {
            for(int j = 0;j <= i / n;j ++)
            {
                for(int k = 0;k <= i / m;k ++)
                {
                    if(j * n + k * m == i) 
                    {
                        st[i] = true;
                    }

                }
            }


    }
    for(int i = N;i >= 0;i --)
    {
        if(!st[i])
        {
            res = i;
            break;
        }
    }
    cout << res;
}

可以证明不能被凑出的最大的数小于 n·m
假设不能被凑出的最大的数大于 n·m 即:x - n · m > 0
说明不存在任何一对a,b和d使得以下式子成立(由于x不能被凑出来所以加上一个d): x = a·n + b·m + d
代入上式计算得到：a·n + b·m + d - m·n > 0即此式不成立,我们可以取a = m,b = n上式变为 m·n + d > 0 可以发现这是必成立的(抛去0)与假设矛盾，所以x一定小于nm
#include <iostream>
#include <algorithm>
using namespace std;
int n, m, minn, maxx, ans;
bool dp[1000000];
int main() {
    cin >> n >> m;
    dp[0] = true;
    minn = min(n, m);
    maxx = max(n, m);
    ans = 1;
    for (int i = minn; i < n * m; i++) {
        if (dp[i - minn])//把minn的倍数置true
        {
            dp[i] = true;
        }
        //比maxx小的数可以组成的已置成true
        else if (i >= maxx && dp[i - maxx])//将maxx的倍数以及可以被i-maxx 整除的置true
        {
            dp[i] = true;
        } 
        else
        {
            ans = i;
        }
    }
    cout << ans;
    return 0;
}

#include <iostream>

using namespace std;
const int N = 100010;
long long a[N],s[N];
int n,k,cnt;
int main()
{
    cin >> n >> k;
    for(int i = 1;i <= n;i ++) cin >> a[i];
    for(int i = 1;i <= n;i ++)//前缀和数组
    {
        a[i] = a[i - 1] + a[i];
    }
    long long res = 0;
    s[0] = 1;//mod k 等于0，说明本身就是k的倍数，应直接加上
    for(int i = 1;i <= n;i ++)
    {
        res += s[a[i] % k];//这俩行代码是先统计（出现与当前值求余的结果相同的元素个数）
        s[a[i] % k] ++;    //再累加（累加当前的值求余的结果,并储存进cnt中），当只有一次非0余数时，不加
    }
    cout << res << endl;
    return 0;
}