题目整理之线性dp

周赛137_D小苯的序列涂色#includebits/stdc.h #define int long long #define fi first #define se second using namespace std; const int mod1e97; typedef pairint,intpii; const int N3e5; int dx[4]{1,-1,0,0}; int dy[4]{0,0,1,-1}; int num[N],inv[N];//阶乘以及阶乘的逆元 //ansnum[a]*inv[a-b]%mod*inv[b]%mod; int kmi(int a,int b){ int res1; while(b){ if(b1)resres*a%mod; b1; aa*a%mod; } return res; } void init(){ num[0]1,inv[0]1; for(int i1;i2e5;i){//预处理出2e5内的阶乘以及其逆元 num[i]num[i-1]*i%mod; inv[i]kmi(num[i],mod-2); } } /* 定义dpi为将前i个全然红的最小代价 我从右到左枚举开始染的地方 假设从l开始染 由于可以重复染色 那么dpi的上一个状态可以是l到i的任意一个数 那我肯定取这几个状态里面最小的开始转移因为我l是枚举出来的定值 我肯定希望上个状态越小越好 */ void solve(){ int n;cinn; vectorinta(n1),s(n10),dp(n10,1e18); for(int i1;in;i){ cina[i]; s[i]s[i-1]^a[i]; } dp[0]0; for(int i1;in;i){ int minx1e18; for(int li;l1;l--){ minxmin(dp[l-1],minx); int c(s[i]^s[l-1]); dp[i]min(dp[i],minxc); } } coutdp[n]; } signed main(){ ios_base::sync_with_stdio(false); cin.tie(0),cout.tie(0); int T1;cinT; while(T--){ solve(); coutendl; } return 0; }牛客周赛 Round 138E小苯的数字染色#includebits/stdc.h #define int long long #define fi first #define se second using namespace std; const int mod1e97; typedef pairint,intpii; const int N3e5; int dx[4]{1,-1,0,0}; int dy[4]{0,0,1,-1}; int num[N],inv[N];//阶乘以及阶乘的逆元 //ansnum[a]*inv[a-b]%mod*inv[b]%mod; int kmi(int a,int b){ int res1; while(b){ if(b1)resres*a%mod; b1; aa*a%mod; } return res; } void init(){ num[0]1,inv[0]1; for(int i1;i2e5;i){//预处理出2e5内的阶乘以及其逆元 num[i]num[i-1]*i%mod; inv[i]kmi(num[i],mod-2); } } /* dp[i]代表处理完前i个数能得到的最大价值 a[i]为奇数时mx[1]从前面的某个奇数开始转移到i能得到的最大价值为mx[1]a[i] */ void solve(){ int n;cinn; vectorinta(n10),dp(n10); for(int i1;in;i) cina[i]; dp[0]0; int f(a[1]%22)%2; vectorintmx(2,-1e18);//能转移过来的最大值 mx[f]dp[0]a[1]; dp[1]0;//1染色不了 for(int i2;in;i){ dp[i]dp[i-1]; int f(a[i]%22)%2; dp[i]max(dp[i],mx[f]a[i]); mx[f]max(mx[f],dp[i-1]a[i]); } coutdp[n]; } signed main(){ ios_base::sync_with_stdio(false); cin.tie(0),cout.tie(0); int T1;cinT; while(T--){ solve(); coutendl; } return 0; }