• <noscript id="e0iig"><kbd id="e0iig"></kbd></noscript>
  • <td id="e0iig"></td>
  • <option id="e0iig"></option>
  • <noscript id="e0iig"><source id="e0iig"></source></noscript>
  • week14作業E Q老師度假

    標簽: 矩陣快速冪DP  c++

    忙碌了一個學期的 Q老師 決定獎勵自己 N 天假期。

    假期中不同的穿衣方式會有不同的快樂值。

    已知 Q老師 一共有 M 件襯衫,且如果昨天穿的是襯衫 A,今天穿的是襯衫 B,則 Q老師 今天可以獲得 f[A][B] 快樂值。

    在 N 天假期結束后,Q老師 最多可以獲得多少快樂值?

    輸入:

    輸入文件包含多組測試樣例,每組測試樣例格式描述如下:

    第一行給出兩個整數 N M,分別代表假期長度與 Q老師 的襯衫總數。(2 ≤ N ≤ 100000, 1 ≤ M ≤ 100)

    接下來 M 行,每行給出 M 個整數,其中第 i 行的第 j 個整數,表示 f[i][j]。(1 ≤ f[i][j] ≤ 1000000)
    測試樣例組數不會超過 10。

    輸出:

    每組測試樣例輸出一行,表示 Q老師 可以獲得的最大快樂值。

    樣例輸入:
    3 2
    0 1
    1 0
    4 3
    1 2 3
    1 2 3
    1 2 3

    樣例輸出:
    2
    9

    f[i][j]表示第 i 天,穿的衣服為 j 所獲得的快樂值總和。
    在這里插入圖片描述在這里插入圖片描述
    這題最關鍵的是想到把累加替換為max,乘法替換為加法。
    因為矩陣快速冪要求矩陣乘法具有結合律,而這樣替換滿足要求,所以可以用矩陣快速冪。

    #include<iostream>
    #include<string.h>
    #include<algorithm>
    #define ll long long
    using namespace std;
    const int N=110;
    int f[110][110];
    int dp[110000][110];
    struct Matrix{
    	ll x[N][N];
    	Matrix operator*(const Matrix& t)const
    	{
    		Matrix ret;
    		for(int i=0;i<N;i++)
    		{
    			for(int j=0;j<N;j++)
    			{
    				for(int k=0;k<N;k++)
    				{
    					ret.x[i][j]=max(ret.x[i][j],x[i][k]+t.x[k][j]); 
    				}
    			}
    		}
    		return ret;
    	}
    	Matrix() 
    	{
    		memset(x,0,sizeof(x));
    	}
    	Matrix(const Matrix& t)
    	{
    		memcpy(x,t.x,sizeof(x));
    	}
    };
    Matrix quick_pow(Matrix a,int x)
    {
    	Matrix ret;
    	memset(ret.x,0,sizeof(ret.x));//定義了新的運算后,單位矩陣變成了全零 
    	while(x)
    	{
    		if(x&1)
    		{
    			ret=ret*a;
    		}
    		a=a*a;
    		x>>=1;
    	}
    	return ret;
    }
    int main()
    {
    	int n,m;
    	while(cin>>n>>m)
    	{
    		memset(f,0,sizeof(f));
    		memset(dp,0,sizeof(dp));
    		for(int i=0;i<m;i++)
    		{
    			for(int j=0;j<m;j++)
    			{
    				cin>>f[i][j];
    			}
    		} 
    		Matrix t1,t2;
    		for(int i=0;i<m;i++)
    		{
    			for(int j=0;j<m;j++)
    			{
    				t1.x[i][j]=f[i][j];
    			}
    		}
    		t2=quick_pow(t1,n-1);
    		ll ans=0;
    		for(int i=0;i<m;i++)
    		{
    			for(int j=0;j<m;j++)
    			{
    				ans=max(ans,t2.x[i][j]);//找出所有方案中的最大值 
    			}
    		}
    		cout<<ans<<endl;
    	}
    }
    
    版權聲明:本文為qq_45639151原創文章,遵循 CC 4.0 BY-SA 版權協議,轉載請附上原文出處鏈接和本聲明。
    本文鏈接:https://blog.csdn.net/qq_45639151/article/details/106313628

    智能推薦

    Week14—度假襯衫選擇

    問題描述 忙碌了一個學期的 Q老師 決定獎勵自己 N 天假期。 假期中不同的穿衣方式會有不同的快樂值。 已知 Q老師 一共有 M 件襯衫,且如果昨天穿的是襯衫 A,今天穿的是襯衫 B,則 Q老師 今天可以獲得 f[A][B] 快樂值。 在 N 天假期結束后,Q老師 最多可以獲得多少快樂值? 【輸入】 輸入文件包含多組測試樣例,每組測試樣例格式描述如下: 第一行給出兩個整數 N M,分別代表假期長度...

    WEEK14 周記 作業——矩陣快速冪_必做題3-Q老師的考驗

    一、題意 1.簡述 Q老師 對數列有一種非同一般的熱愛,尤其是優美的斐波那契數列。 這一天,Q老師 為了增強大家對于斐波那契數列的理解,決定在斐波那契的基礎上創建一個新的數列 f(x) 來考一考大家。數列 f(x) 定義如下: 當 x < 10 時,f(x) = x; 當 x ≥ 10 時,f(x) = a0 * f(x-1) + a1 * f(x-2) + a2 * f(x-3) +...

    [week14] D - Q老師染磚(選做) —— 矩陣快速冪優化DP

    文章目錄 題意 Input Output 輸入樣例 輸出樣例 提示 分析 總結 代碼 題意 衣食無憂的 Q老師 有一天突發奇想,想要去感受一下勞動人民的艱苦生活。 具體工作是這樣的,有 N 塊磚排成一排染色,每一塊磚需要涂上紅、藍、綠、黃這 4 種顏色中的其中 1 種。且當這 N 塊磚中紅色和綠色的塊數均為偶數時,染色效果最佳。 為了使工作效率更高,Q老師 想要知道一共有多少種方案可以使染色效果最...

    Week14 作業

    目錄 1.A - Q老師與石頭剪刀布(必做) 2.B - Q老師與十字叉(必做) 3.C - Q老師的考驗(必做) 1.A - Q老師與石頭剪刀布(必做) 題意 每一個大人曾經都是一個小孩,Q老師 也一樣。 為了回憶童年,Q老師 和 Monika 玩起了石頭剪刀布的游戲,游戲一共 n 輪。無所不知的 Q老師 知道每一輪 Monika 的出招,然而作為限制, Q老師 在這 n 輪游戲中必須恰好出 a...

    week14作業

    B - Q老師與十字叉(必做) 解題思路: 首先,這個題目并不是很難,第一反應是和我們第三次csp模擬的第二題有些類似,一開始也就直接對每個點進行暴力遍歷,但這道題目的數據量偏大,這樣肯定會TLE。我們應當采取更有效的做法。其實對于一個點的檢驗便是對一行一列的檢驗,我們不能簡單的當用到某一行某一列時才去計算它,這樣會有很多的重復性工作,我們可以將每一行每一列計算好等待備用。我對這道題目感觸比較大的...

    猜你喜歡

    week14 作業

    文章目錄 A Q老師與石頭剪刀布 思路 總結 代碼 B Q老師與十字叉 思路 總結 代碼 C Q老師的考驗 思路 代碼 D Q老師染磚 思路 E Q老師度假 思路 代碼 A Q老師與石頭剪刀布 思路 對方若出剪刀,那么有石頭出石頭,沒有石頭用’$'標記這一局的出手 對方若出石頭,那么有布出布,沒有布用’$'標記這一局的出手 對方若出布,那么有剪刀出剪刀,沒有剪刀用&rsqu...

    Week 14 C - Q老師的考驗

    Q老師的考驗 Q老師 對數列有一種非同一般的熱愛,尤其是優美的斐波那契數列。 這一天,Q老師 為了增強大家對于斐波那契數列的理解,決定在斐波那契的基礎上創建一個新的數列 f(x) 來考一考大家。數列 f(x) 定義如下: 當 x < 10 時,f(x) = x; 當 x ≥ 10 時,f(x) = a0 * f(x-1) + a1 * f(x-2) + a2 * f(x-3) + &h...

    Week14 E 貓睡覺問題

    Week14 E 題目 思路 代碼 題目 思路 首先是題意確實難理解,他是屬于每天循環一個時間表,也就是這個時間表不一定從0時開始(上一天可能熬夜了)。然后就是如果可以連續工作24h的話時間表上并不能一整體都不睡覺(加上下一天就是48h了) 主要步驟 將時間轉化為數值并排序 從第一個事件的開始模擬到第一個事件開始前(比如說5:00開始,就模擬到下一天的4:59) 如果兩個事件中間的休息時間小于睡眠...

    Week14-C-Q老師的考驗

    題目描述: Q老師 對數列有一種非同一般的熱愛,尤其是優美的斐波那契數列。 這一天,Q老師 為了增強大家對于斐波那契數列的理解,決定在斐波那契的基礎上創建一個新的數列 f(x) 來考一考大家。數列 f(x) 定義如下: 當 x < 10 時,f(x) = x; 當 x ≥ 10 時,f(x) = a0 * f(x-1) + a1 * f(x-2) + a2 * f(x-3) + &he...

    數組刪除其中某個對象的方法

    數組刪除其中的對象或元素,在前端是比較常見的需求。 我現在比較常用的方法如下: 這種方法只適合刪除具有唯一標識的對象。 有沒有想要脫單的小伙伴,加入我們的脫單星球,認識更多優秀的小哥哥小姐姐 特此聲明,星球是免費的,但是創建星球的時候說是必須輸入金額,所以只能先私聊,我再加你免費加入!...

    精品国产乱码久久久久久蜜桃不卡