Educational Codeforces Round 139 (Rated for Div. 2)
Problem - 1766E - Codeforces
顯然我們可以把0序列的貢獻(xiàn)單獨(dú)算: i*(n-i+1)?
考慮只存在1,2,3的情況.
首先通過(guò)，觀察到一個(gè)重要性質(zhì):
最多只有三種序列.
- 含有3或純1或純2型.
- 純1或純2型
- 純2或純1型
我們每次添加元素的操作，只跟上一個(gè)位置序列的最后一個(gè)元素有關(guān)
每個(gè)位置最多有3種類(lèi)型的序列,所以每個(gè)位置的狀態(tài)數(shù)是很有限的，這個(gè)很重要！
設(shè) dp[i][j][k][l] 表示 以i為右端點(diǎn)的且當(dāng)前序列狀態(tài)為 (j,k,l) 的區(qū)間數(shù)量.
轉(zhuǎn)移：
當(dāng)前位置為? b[i],? 枚舉上一個(gè)位置的狀態(tài)(j,k,l)
轉(zhuǎn)移方程為:
?文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-460353.html
?
AC代碼：文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-460353.html
#include <bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
#define int long long
#define endl '\n'
#define bit(x) (1ll << x)
using namespace std;
const int N = 3 * 1e3 + 5;
const int inf = 1e16;
int dp[7][7][7][7];
void solve()
{
int n;
cin >> n;
vector<int> a(n + 1), b(n + 1);
int ans = 0;
for (int i = 1; i <= n; i++)
{
cin >> b[i];
}
int now = 0;
int nex = 0;
for (int i = 1; i <= n; i++)
{
dp[now][0][0][0]++;
if (b[i] == 0)
{
ans += i * (n - i + 1);//單獨(dú)統(tǒng)計(jì)0序列的貢獻(xiàn)，其他狀態(tài)由上一個(gè)轉(zhuǎn)移，沒(méi)變
}
else
{
nex = now^1;
for (int j = 0; j <= 3; j++)
for (int k = 0; k <= 3; k++)
for (int l = 0; l <= 3; l++)
{
dp[nex][j][k][l] = 0;
}
for (int j = 0; j <= 3; j++)
{
for (int k = 0; k <= 3; k++)
{
for (int l = 0; l <= 3; l++)
{
if (j == 0 || (j & b[i]))//當(dāng)j == 0 (開(kāi)新序列)或 b[i]于j有交集（維護(hù)序列最后一個(gè)值）
{
dp[nex][b[i]][k][l] += dp[now][j][k][l];
}
else if (k == 0 || (k & b[i]))//同上
{
dp[nex][j][b[i]][l] += dp[now][j][k][l];
}
else
{
dp[nex][j][k][b[i]] += dp[now][j][k][l];
}
}
}
}
now = nex;
}
for (int j = 0; j <= 3; j++)
{
for (int k = 0; k <= 3; k++)
{
for (int l = 0; l <= 3; l++)
{
ans += dp[now][j][k][l] * ((j > 0 ? 1 : 0) + (k > 0 ? 1 : 0) + (l > 0 ? 1 : 0));
}
}
}
}
cout << ans << endl;
}
q
signed main()qq
{
/*ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);*/
int t = 1;
// cin >> t;
while (t--)
{
solve();
}
return 0;
}q到了這里，關(guān)于Educational Codeforces Round 139 (Rated for Div. 2)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
