76.最大效益

问题描述

明明的爸爸开了一家小公司，公司里有5名职员。今天，公司接待了5位客户。明明的爸爸知道，和任何一位客户谈判并签下合同都要花一整天的时间，而他又希望在一天之内，和这5位客户都签好合同。因此，明明的爸爸要求公司里的5名职员分别与1位客户谈判。

明明的爸爸也知道，这5名职员和5位客户的性格各不相同。因此，不同的职员与不同的客户谈判，会给公司带来不同的经济效益。他现在要做出一个决策，让5名职员分别与哪位客户谈判，才能让公司今天的总经济效益最大。

明明的爸爸首先做了一张5行5列的效益表，如下所示：

1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1

在这张效益表中，每行代表一名公司职员，每列代表一个客户，每行中的5个数字就表示了当该行所代表的公司职员和每位客户谈判时所能产生的效益。明明的爸爸就要通过这张效益表来决定哪位职员与哪位顾客谈判，然后能够使公司的效益最大。就拿上面这张表来看，由于无论哪位职员与哪位客户谈判，所产生的效益都是1，因此最大的效益就是5。这是最简单的一种情况，但是当效益表里的数字变得复杂，就很难进行选择，到底哪种组合方式才是最优的。因此明明的爸爸求助于你，帮助他解决这个问题。

明明的爸爸的问题可以归结为：给你一张5行5列的效益表，表中的数字均为大于等于0的整数，要求在这张表中选出5个数字，使这5个数字的和最大。（注：这5个数字分别来自表中的不同行不同列，即同一行只能选择一个数字，同一列也只能选择一个数字。）

个人总结

初见以为是dp，但想了半天构造不出状态转移方程，最后想到了

dp[i][j] i代表考虑前n行，j指向对应的已经使用的列号集合mask[i][j]={前i行已经用过的列}，dp[i][j]等于考虑前n行的最大效益

问了AI说思路是对的，但是我自己实际写起来头直接晕了，搞不清楚三个数组的i，j，mask[i][j]对应的含义，状态转移方程也写不明白。

5x5的数据范围确实可以穷举，但我最后用了dfs，dfs应该是本题最优解，实现起来思路也很顺畅

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<vector<int>> a(5,vector<int>(5,0));
vector<bool> used(5,false);
int max_sum;

void dfs(int row,int sum){
    if(row>=5){
        if(sum>max_sum)
            max_sum=sum;
        return;
    }
    for(int j=0;j<5;j++){
        if(!used[j]){
            used[j]=true;
            dfs(row+1,sum+a[row][j]);
            used[j]=false;
        }
    }
}

int main(){
    while(cin>>a[0][0]){
        max_sum=0;
        used={false,false,false,false,false};
        for(int i=0;i<5;i++){
            for(int j=0;j<5;j++){
                if(i!=0||j!=0)
                    cin>>a[i][j];
            }
        }
        dfs(0,0);
        cout<<max_sum<<endl;
    }

}

77.螺旋方阵

问题描述

明明在上学的时候，参加数学兴趣班。在班上，老师介绍了一种非常有趣的方阵，称之为螺旋方阵。该方阵一共由n×n个正整数构成（我们称之为n阶螺旋方阵），即共有n行n列。

方阵中的数字从1开始递增，数字的排序规则是从左上角出发由1开始排序，并按顺时针方向旋进，即先排最外面的一圈，然后排里面的一圈，以此类推，直到排到最后一个数为止。

例如一个4阶的螺旋方阵，一共有4×4=16个正整数构成，数字从1递增到16，最后排出来的方阵如下：

 1  2  3  4

12 13 14  5

11 16 15  6

10  9  8  7

明明回家后想自己动手构造这样的螺旋方阵。他从n=1开始构造，但是他发现当n越来越大时，螺旋方阵的复杂性就越高，然后构造出来的方阵就越容易出错。为了降低构造方阵的出错率，提高构造速度，明明就求助于你，请你帮他写一个程序，来构造螺旋方阵。 明明的问题可以归结为：给你一个正整数n，请你按题目描述中所述的方法，构造出n阶的螺旋方阵。

#include <iostream>
#include <vector>


using namespace std;

int main(){
    int n;
    while(cin>>n){
        vector<vector<int>> a(n,vector<int>(n,0));
        int cnt=0;
        int dir=0;//0右，1下，2左，3上
        int flag=n;//当cnt走到几时该转向
        int k=0;//与n-k一起使用，决定再走n-k步到下一个转弯点
        for(int i=0,j=0;cnt<n*n;){
            a[i][j]=++cnt;
            if(cnt==flag){
                dir=(dir+1)%4;
                if(dir==1 || dir==3)
                    k++;
                flag+=n-k;
            }
            switch(dir){
                case 0:j++;break;
                case 1:i++;break;
                case 2:j--;break;
                case 3:i--;break;
            }
        }

        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(j!=0)
                    cout<<" ";
                cout<<a[i][j];
            }
            cout<<endl;
        }
    }

}

78.方块转换

作者: xxx

时间限制: 1s

章节: 二维数组

问题描述

一块N x N（1=<N<=10）正方形的黑白瓦片的图案要被转换成新的正方形图案。

写一个程序来找出将原始图案按照以下列转换方法转换成新图案的最小方式：

#1：转90度：图案按顺时针转90度。

#2：转180度：图案按顺时针转180度。

#3：转270度：图案按顺时针转270度。

#4：反射：图案在水平方向翻转（形成原图案的镜像）。

#5：组合：图案在水平方向翻转，然后按照#1-#3之一转换。

#6：不改变：原图案不改变。

#7：无效转换：无法用以上方法得到新图案。

如果有多种可用的转换方法，请选择序号最小的那个。

比如：

转换前：

 @-@
 ---
 @@-

转换后：
 @-@
 @--
 --@

这种转换采取#1（按顺时针转90度）即可。

注意：图案中的字符“@”和“-”在转90度后，还是“@”和“-”。不要认为“-”转90度后变成“|”。

个人总结

总计6+3=9种结果，穷举对比即可。写起来有点麻烦，具体移动细节要清楚的手算出来

#include <iostream>
#include <vector>



using namespace std;

int n;
vector<vector<char>> mov(vector<vector<char>> a,int method)
{
    vector<vector<char>> c(n,vector<char>(n,0));
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<n; j++)
        {
            switch(method)
            {
            case 1:
                c[i][j]=a[n-j-1][i];
                break;
            case 2:
                c[i][j]=a[n-i-1][n-j-1];
                break;
            case 3:
                c[i][j]=a[j][n-i-1];
                break;
            case 4:
                c[i][j]=a[i][n-j-1];
                break;
            }

        }
    }
    return c;
}

bool isMatch(vector<vector<char>> a,vector<vector<char>> b)
{
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<n; j++)
        {
            //cout<<a[i][j]<<" "<<b[i][j];
            if(a[i][j]!=b[i][j])
                return false;
        }
    }
    return true;
}

int main()
{
    cin>>n;
    vector<vector<char>> a(n,vector<char>(n,0));
    vector<vector<char>> b(n,vector<char>(n,0));
    vector<vector<char>> c(n,vector<char>(n,0));
    vector<vector<char>> t(n,vector<char>(n,0));
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<n; j++)
        {
            cin>>a[i][j];
        }
    }

    for(int i=0; i<n; i++)
    {
        for(int j=0; j<n; j++)
        {
            cin>>b[i][j];
        }
    }


    for(int i=1; i<=4; i++) //#1~4逐个试
    {
        c=mov(a,i);
        if(isMatch(c,b))
        {
            cout<<i<<endl;
            return 0;
        }
    }

    t=mov(a,4);
    for(int i=1; i<=3; i++) //图案在水平方向翻转，然后按照#1-#3之一转换。
    {
        c=mov(t,i);
        if(isMatch(c,b))
        {
            cout<<'5'<<endl;
            return 0;
        }
    }

    if(isMatch(a,b))
    {
        cout<<'6'<<endl;
        return 0;
    }

    cout<<'7'<<endl;
}

计算机英语扇贝打卡