-
H 重建道路
一道区间DP好题
一开始以为有多种不同的括号匹配次序而导致自己一头大雾wuw，首先看到括号匹配就要想到用栈来求出每个括号对应的匹配项，对于一个区间来说，其左括号一定是具有与之对应的右括号存在时染色才有意义，所以我们要求出每个括号对应的位置\(should[i]\)，首先设出状态表达式为：\(dp[l][r][i][j]\) 也就是 \(l~r\) 区间，两端点的染色方案为\(i和j\)
接下来考虑如何求出方案数：
对于一个相邻的完整括号即：（）
这种我们的染色的方案数一定是对于每种情况都是一种，即：
\(dp[l][r][0][1]=dp[l][r][1][0]=dp[l][r][2][0]=dp[l][r][0][2]=1\)
接下来考虑左括号与右括号相匹配，那么这种情况我们要求在这个区间内的所有括号的染色方案数均被求出，这样我们才能向外扩展，也就是从\(l+1\)扩展到\(l\)，对于这种情况下的状态转移如何求？很明显我们只需要考虑某一个端点中的相邻括号的颜色即可，这里拿左端点为例：若左端点\(l\)为颜色\(1\)，那么其\(l+1\)的颜色不可为\(1\)，那么此时我们有：
\(dp[l][r][1][0]=dp[l+1][r-1][2][0]+dp[l+1][r-1][0][1]+dp[l+1][r-1][0][2]\)
其它情况同理
对于左端点和右端点的括号不匹配，那么我们就需要寻找左端点对应匹配的位置，并且其相邻位置不应该同色，那么就有：
\(for(int i=0;i<=2;i++)\)
\(for(int j=0;j<=2;j++)\)
\(for(int e=0;e<=2;e++)\)
\(for(int k=0;k<=2;k++)\)
$ if(j==e and j>0 ) continue$
\(dp[l][r][i][k]=(dp[l][r][i][k]+dp[l][should[l]][i][j]*dp[should[l]+1][r][e][k]%mod)%mod\)
为什么是相乘呢？因为左区间所有的情况只适用于右区间的一种情况，也就是乘法原理，不懂的可以去看下，至此就结束了
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1000,mod=1e9+7;
int dp[N][N][5][5];
signed main()
{
std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
string s; cin>>s;
stack<int>stk;
int n=s.size();
vector<int>should(n+1);
for(int i=0;i<n;i++){
if(s[i]=='(') stk.push(i+1);
else should[i+1]=stk.top(),should[stk.top()]=i+1,stk.pop();
}
function<void(int,int)>dfs;
dfs=[&](int l,int r)->void{
if(l==r-1) dp[l][r][0][1]=dp[l][r][1][0]=dp[l][r][2][0]=dp[l][r][0][2]=1;
else if(r==should[l]){
dfs(l+1,r-1);
for(int i=0;i<=2;i++){
for(int j=0;j<=2;j++){
if(i!=1) dp[l][r][1][0]=(dp[l][r][1][0]+dp[l+1][r-1][i][j])%mod;
if(i!=2) dp[l][r][2][0]=(dp[l][r][2][0]+dp[l+1][r-1][i][j])%mod;
if(j!=1) dp[l][r][0][1]=(dp[l][r][0][1]+dp[l+1][r-1][i][j])%mod;
if(j!=2) dp[l][r][0][2]=(dp[l][r][0][2]+dp[l+1][r-1][i][j])%mod;
}
}
}
else{
dfs(l,should[l]),dfs(should[l]+1,r);
for(int i=0;i<=2;i++){
for(int j=0;j<=2;j++){
for(int e=0;e<=2;e++){
for(int k=0;k<=2;k++){
if(j&&e&&j==e) continue;
dp[l][r][i][k]=(dp[l][r][i][k]+dp[l][should[l]][i][j]*dp[should[l]+1][r][e][k]%mod)%mod;
}
}
}
}
}
};
dfs(1,n);
int res=0;
for(int i=0;i<=2;i++)
for(int j=0;j<=2;j++)
res=(res+dp[1][n][i][j])%mod;
cout<<res<<'\n';
return 0;
}
-
Shuffling Songs
这是我比赛的时候遇到的一道题目，当时没做出来，首先先看数据范围，这么小大概率是状压，然后考虑如何转移，对于所有的状态，我们可以枚举以歌曲\(j\)结尾时候的方案数，那么显然设出状态表达：\(dp[i][j]\) 为 状态 ｉ 的时候以ｊ结尾的方案数，然后枚举状态即可，如果状态ｉ中含有歌曲或作者ｊ那么直接跳过，如果不包含且两者可以合并，那么就让ｊ做为新的结尾，并且方案数加１，如何求出方案数？直接看二进制状态中有多少个１即可
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10,mod=1e9+7;
void solve(){
int n; cin>>n;
vector<string>s(n+1),g(n+1);
for(int i=1;i<=n;i++) cin>>s[i]>>g[i];
vector<vector<bool>>ok(n+1,vector<bool>(n+1,false));
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(s[i]==s[j]||g[i]==g[j])
ok[i][j]=true; //两个可以加,标记一下
}
}
vector<vector<bool>>dp(1<<n|1,vector<bool>(n+1,false));
int res=0;
for(int i=1;i<=n;i++) dp[1<<(i-1)][i]=true;
for(int k=0;k<(1<<n);k++){
for(int i=1;i<=n;i++){
if(dp[k][i]){ //若k状态可以以i结尾,那么考虑可不可以用继续加
res=max(res,(int)__builtin_popcount(k));//先把此时的方案数求出
for(int j=1;j<=n;j++){
if(!(k&(1<<(j-1)))&&ok[i][j])
dp[k|(1<<(j-1))][j]=true; //可以加,就加
}
}
}
}
cout<<n-res<<'\n';
}
signed main(){
std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);int t;cin>>t;while(t--)solve();
}
-
Rudolf and k Bridges
一眼单调队列优化\(dp\)，为什么？因为很明显我们在建桥的过程中要尽可能的选消耗小的材料，那么对于一段区间\([i-d,i]\)我们肯定要选择最小的消耗，那么就需要单调队列来维护了，由于需要求出连续的值，用前缀和维护一下即可
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10,mod=1e9+7;
void solve(){
int n,m,k,d; cin>>n>>m>>k>>d;
d++;
vector<int>num(n+1);
int res=1e18;
for(int i=1;i<=n;i++){
vector<int>a(m+1);
for(int j=1;j<=m;j++) cin>>a[j],a[j]++;
vector<int>q(m+1),dp(m+1,1e18);
dp[1]=1;
int hh=1,tt=0;
for(int j=2;j<=m;j++){
while(hh<=tt&&j-q[hh]>d) hh++;
while(hh<=tt&&dp[j-1]<=dp[q[tt]]) tt--;
q[++tt]=j-1,dp[j]=dp[q[hh]]+a[j];
}
num[i]=num[i-1]+dp[m];
if(i>=k) res=min(res,num[i]-num[i-k]);
}
cout<<res<<'\n';
}
signed main(){
std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);int t;cin>>t;while(t--)solve();
}
-
[USACO11OPEN] Mowing the Lawn G
首先考虑暴力，设我们当前在位置ｉ，那么我们此时能够获得的最大贡献为\(dp[i]\)，且有：
我们可以在区间 \([i-K,i]\) 间枚举休息的奶牛,所以转移方程就可以初步推出
用前缀和优化一下的话就是：
\[dp[i]=max\{dp[j-1]+Sum[i]-Sum[j]\}\ \ \ (i-K\leq j\leq i) \]此时的复杂度为\(O(n*k)\)很明显还是不可以
由于\(sum[i]\)不变，只需要求出\([i-k,i]\)这段区间最大的\(dp[j-1]+sum[j]\)即可，故使用单调队列优化即可
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10,mod=1e9+7;
signed main()
{
std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int n,k; cin>>n>>k;
vector<int>e(n+1),s(n+1);
for(int i=1;i<=n;i++) cin>>e[i],s[i]=s[i-1]+e[i];
vector<int>q(n+1),dp(n+1),_(n+1);
int hh=1,tt=0;
for(int i=1;i<=n;i++){
while(hh<=tt&&i-q[hh]>k) hh++;
while(hh<=tt&&dp[i-1]-s[i]>=_[q[tt]]) tt--;
q[++tt]=i,_[i]=dp[i-1]-s[i];
if(i>k) dp[i]=_[q[hh]]+s[i];
else dp[i]=s[i];
}
cout<<dp[n]<<'\n';
return 0;
}