游戲通關(guān)了，把暑假?zèng)]有AC的pokemon再看了一遍。
能過師兄的數(shù)據(jù)，但仍不能AC
思路二：
總體思路：記錄兩兩互質(zhì)所有狀況，記錄權(quán)重，用權(quán)重判斷數(shù)據(jù)的取舍。
（1）引入權(quán)重的概念，兩重循環(huán)遍歷數(shù)據(jù)，判斷兩兩互質(zhì)的數(shù)量。并將權(quán)重記錄下來。
如：7 6 5 4 3 2 1中，7與其他任何一個(gè)數(shù)都互質(zhì)，所以他的權(quán)重是6，而6與4 3 2 都不互質(zhì)，所以權(quán)重為3.
（2）記錄7 6 5 4 3 2 1互質(zhì)的情況，如果7與6互質(zhì)，就判定為1，并記錄，否則判定為0。（好像是狀態(tài)壓縮的概念，但我沒學(xué)過狀態(tài)壓縮）
（3）排序權(quán)重，將權(quán)重高的排在前面，權(quán)重低的排在后面，避免因?yàn)檫壿媶栴}反而把權(quán)重高的舍棄了。（比如，a權(quán)重為7，b權(quán)重為6，c權(quán)重為6, d權(quán)重為8，如果先判斷a，把b，c舍棄了，如果b,c和d是互質(zhì)的，b,c被舍棄后d權(quán)重會(huì)下降變成6，c就會(huì)被舍棄。）
（4）如果兩個(gè)數(shù)不互質(zhì)，就通過權(quán)重比較舍棄數(shù)據(jù)
代碼如下：

#include<iostream>
using namespace std;

long long gcd(long long a, long long b) {
    return b ? gcd(b, a % b) : a;
}

void niubi(int n, long long a[20][20])
{
    long long i, j;
    for (i = 0; i < n; i++)
    {
        for (j = 0; j < n; j++)
        {
            if (a[i][0] != 0 && a[j][0] != 0)
            {
                if (gcd(a[i][0], a[j][0]) == 1)//判斷兩個(gè)數(shù)是否互質(zhì)，如果互質(zhì)
                {
                    a[i+1][j+1] = 1;
                }
                else
                {
                    a[i+1][j+1] = 0;
                }
            }
        }
    }
}

int main()
{
    int T;
    int n;
    int i, j,k;
    int sum;
    long long temp;
    long long a[20][20] = {0};
    long long dp[20] = {0};
    int ins[20];
    //用二維數(shù)組記錄，第一個(gè)維度代表著輸入的數(shù)據(jù)，第二個(gè)維度代表數(shù)據(jù)互質(zhì)狀況，第二個(gè)維度末尾的一位代表著權(quán)重，
    //互質(zhì)為1，不互質(zhì)為0，數(shù)據(jù)加起來的總和即為權(quán)重
    cin >> T;
    
        while (T--)
        {
            

            cin >> n;
            sum = 0;
            memset(a, 0, sizeof(a));
            for (j = 0; j < n; j++)
            {
                cin >> a[j][0];//在第0位輸入對應(yīng)的數(shù)據(jù)
                a[0][j] = a[j][0];
            }

            for (j = 0; j <= n; j++)
                ins[j] = j;//初始化對應(yīng)坐標(biāo)

            niubi(n, a);


            for (i = 1; i <= n; i++)//計(jì)算權(quán)重
                for (j = 1; j <= n; j++)
                {
                    a[j][n + 1] += a[i][j];
                    dp[j] = a[j][n + 1];
                }


            for (i = 1; i <= n; i++)//給權(quán)重坐標(biāo)排序
            {
                for (j = 1; j <= n; j++)
                {                   
                    if (dp[i] > dp[j])
                    {
                        temp = dp[i];
                        dp[i] = dp[j];
                        dp[j] = temp;

                        temp = ins[j];
                        ins[j] = ins[i];
                        ins[i] = temp;

                    }
                }                           
            }

            /*for (i = 1; i <= n; i++)
                cout <<"\t"<< a[0][i-1];
            cout << endl;*/

            /*for (i = 1; i <=n+1; i++)
            {
                cout<< a[i-1][0] <<'\t';
                for (j = 1; j <=n; j++)
                    cout << a[j][i] << '\t';
                cout << endl;
            }*/
            //在此之前要將權(quán)重高的排個(gè)序

            /*for (j = 0; j <= n; j++)
                cout << ins[j] << '\t';
            cout << endl<<endl;*/

            for (i = 1; i <= n; i++)
            {
                for (j = 1; j <= n; j++)
                {
                    //cout << a[ins[i]][j] << '\t';
                    if (a[ins[i]][j] == 0 && ins[i] != j&&a[ins[i]][n+1]!=0)
                    {
                        for (k = 1; k <= n + 1;k++) a[j][k]=0;
                    }
                    //cout << a[ins[i]][n + 1] << a[j][n+1] << endl << endl;
                }
                //cout << endl;
                
            }
            /*cout << endl;
            for (i = 1; i <= n; i++)
            {
                for (j = 1; j <= n; j++)
                {
                    cout << a[ins[i]][j] << '\t';
                }
                cout << endl;
            }*/
            for (j = 1; j <=n; j++)
                if (a[j][n+1] != 0) sum++;
            cout << sum << endl;
        }
    
    return 0;
}

運(yùn)行截圖：

image.png

師兄的數(shù)據(jù):

image.png