#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100;
int a[N];
int f[N][N];
int root[N][N];
void dfs(int l,int r){
if(l>r)return;
int k=root[l][r];
cout<<k<<' ';
dfs(l,k-1);
dfs(k+1,r);
}
int main()
{
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i ++ ){
scanf("%d", &a[i]);
f[i][i]=a[i];
root[i][i]=i;
f[i][i-1]=1;
}
f[n+1][n]=1;
for(int w=2;w<=n;w++){
for(int i=1;i+w-1<=n;i++){
int j=i+w-1;
for(int k=i;k<=j;k++){
int t=f[i][k-1]*f[k+1][j]+a[k];
if(t>f[i][j]){
f[i][j]=t;
root[i][j]=k;
}
}
}
}
cout<<f[1][n]<<endl;
dfs(1,n);
cout<<endl;
}
活动打卡代码
AcWing 479. 加分二叉树
活动打卡代码
AcWing 320. 能量项链
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 256;
int a[N];
int f[N][N];
int main()
{
int n;
scanf("%d", &n);
for (int i = 0; i < n; i ++ )scanf("%d",&a[i]);
for(int i=n;i<2*n;i++)a[i]=a[i-n];
for(int w=3;w<=n+1;w++){
for(int i=0;i+w-1<n*2;i++){
int j=i+w-1;
for(int k=i+1;k<j;k++){
f[i][j]=max(f[i][j],f[i][k]+f[k][j]+a[i]*a[k]*a[j]);
}
}
}
int ans=0;
for(int i=0;i<n;i++)ans=max(ans,f[i][i+n]);
cout<<ans;
}
活动打卡代码
LeetCode 32. 最长有效括号
动态规划
忽略边界条件
if s[i]== ')':
if s[i-1]=='(':
dp[i]= dp [i-2]+2
else
dp[i]=dp[i-1]+2+dp[i-dp[i-1]-2]
class Solution {
public:
int longestValidParentheses(string s) {
int n=s.size();
int dp[n+3];
memset(dp,0,sizeof dp);
int ans=0;
for(int i=2;i<=n;i++){
if(s[i-1]==')'){
if(s[i-2]=='(')dp[i]=dp[i-2]+2;
else {
int idx = i-dp[i-1]-2;
if(idx>=0)
if(s[idx]=='(')
dp[i]=dp[i-1]+2+dp[idx];
}
ans=max(ans,dp[i]);
}
}
return ans;
}
};
双向统计
当从左向右时，不考虑形如”((())”,左括号多于右括号的情况
当从右向左时，不考虑形如”(()))”,右括号多于左括号的情况
统计左括号和右括号，相等时更新最值。
假设存在最长括号串S，则S必由”S)“或者“(S”包围
class Solution {
public:
int longestValidParentheses(string s) {
int n=s.size();
int l=0,r=0;
int lcnt=0,rcnt=0;
int ans=0;
while(r<n){
while(r<n&&lcnt>=rcnt){
if (s[r++]=='(')lcnt++;
else rcnt++;
if(lcnt==rcnt)ans=max(ans,lcnt+rcnt);
}
l=r,lcnt=0,rcnt=0;
}
l=r=n-1,lcnt=rcnt=0;
while(l>=0){
while(l>=0&&rcnt>=lcnt){
if(s[l--]=='(')lcnt++;
else rcnt++;
if(lcnt==rcnt)ans=max(ans,lcnt+rcnt);
}
r=l,lcnt=0,rcnt=0;
}
return ans;
}
};
活动打卡代码
AcWing 524. 愤怒的小鸟
思路总结
- $y=ax^2+bx$，要求$a<0$,三个点确定一条抛物线，原点已经确定，另外两个点可以构成$O(n^2)$量级条抛物线
- 预处理出所有的抛物线，判断其所经过的所有点，用bitmap存下来。注意横坐标不能相等，还有只经过一条点的抛物线的特殊处理，可以假设其只经过一个点，因为在最优解中，无非必要，尽量多占几个点。
- 按bitmap从$1$到$1<<n$遍历，注意，只要遍历到第一个未击中的点，用这个点更新即可break。这里可以break的原因如下，假设f[i]的最优解已经知道，则j点是必须经过的，我们遍历所有经过j点的抛物线，最优解一定被包含了。这个地方值得好好玩味一下。
#include <iostream>
#include <cstring>
#include<cmath>
#include <algorithm>
using namespace std;
const int N = 18;
const int M = 1<<N;
int f[M];
double x[N],y[N];
int path[N][N];
int cmp(double a,double b){
if(fabs(a-b)<1e-8)return 0;
else if(a>b)return 1;
else return -1;
}
int main()
{
int t;
cin>>t;
while(t--){
int n,m;
cin>>n>>m;
for (int i = 0; i < n; i ++ ){
cin>>x[i]>>y[i];
}
memset(path,0,sizeof path);
for (int i = 0; i < n; i ++ ){
path[i][i]=1<<i;
for (int j = 0; j < n; j ++ ){
if(!cmp(x[i],x[j]))
continue;
double a = (y[j]/x[j]-y[i]/x[i])/(x[j]-x[i]);
double b = (y[j]/x[j]-a*x[j]);
if(cmp(a,0)>=0)continue;
for(int k = 0;k<n;k++){
if(!cmp(y[k],(a*x[k]+b)*x[k])){
path[i][j]|=(1<<k);
}
}
}
}
memset(f,0x3f,sizeof f);
f[0]=0;
for(int i=0;i+1<1<<n;i++){
for(int j=0;j<n;j++){
if(!((i>>j)&1)){
for(int k=0;k<n;k++){
f[i|path[j][k]]=min(f[i|path[j][k]],f[i]+1);
}
break;
}
}
}
cout<<f[(1<<n)-1]<<endl;
}
}
活动打卡代码
LeetCode 752. 打开转盘锁
struct Node{
int a[4];
};
int dist[10][10][10][10];
Node tar;
class Solution {
public:
static int calc(Node t){
int res=0;
for(int i=0;i<4;i++){
res+=min(abs(t.a[i]-tar.a[i]),10-abs(t.a[i]-tar.a[i]));
}
return dist[t.a[0]][t.a[1]][t.a[2]][t.a[3]]+res;
};
struct cmp{
bool operator()(const Node &a,const Node &b){
return calc(a)>calc(b);
}
};
int openLock(vector<string>& deadends, string target) {
tar={{target[0]-'0',target[1]-'0',target[2]-'0',target[3]-'0'}};
memset(dist,0,sizeof dist);
for(auto &t:deadends){
dist[t[0]-'0'][t[1]-'0'][t[2]-'0'][t[3]-'0']=-1;
}
priority_queue<Node,vector<Node>,cmp> q;
if(dist[0][0][0][0]==-1)return -1;
dist[0][0][0][0]=1;
q.push({{0,0,0,0}});
while(q.size()){
auto t=q.top();
q.pop();
if(t.a[0]==tar.a[0]&&t.a[1]==tar.a[1]&&t.a[2]==tar.a[2]&&t.a[3]==tar.a[3])return dist[t.a[0]][t.a[1]][t.a[2]][t.a[3]]-1;
for(int k=0;k<4;k++){
int d[]={-1,1};
for(int j=0;j<2;j++){
Node tmp=t;
tmp.a[k]+=d[j];
if(tmp.a[k]>=10)tmp.a[k]-=10;
else if(tmp.a[k]<0)tmp.a[k]+=10;
if(dist[tmp.a[0]][tmp.a[1]][tmp.a[2]][tmp.a[3]]==0){
dist[tmp.a[0]][tmp.a[1]][tmp.a[2]][tmp.a[3]]=dist[t.a[0]][t.a[1]][t.a[2]][t.a[3]]+1;
q.push(tmp);
}
}
}
}
return -1;
}
};
活动打卡代码
AcWing 1068. 环形石子合并
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 512;
int a[N];
int f[N][N],g[N][N];
int s[N];
int main()
{
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i ++ ){
scanf("%d", &a[i]);
a[i+n]=a[i];
}
memset(g,0x3f,sizeof g);
for(int i=1;i<=n*2;i++){
s[i]=s[i-1]+a[i];
g[i][i]=0;
}
for(int w=1;w<=n*2;w++){
for(int i=1;i+w-1<=n*2;i++){
int j=i+w-1;
for(int k=i;k<j;k++){
f[i][j]=max(f[i][j],f[i][k]+f[k+1][j]+s[j]-s[i-1]);
g[i][j]=min(g[i][j],g[i][k]+g[k+1][j]+s[j]-s[i-1]);
}
}
}
int minv=0x3f3f3f3f,maxv=-1;
for (int i = 1; i <= n; i ++ )minv=min(g[i][i+n-1],minv),maxv=max(maxv,f[i][i+n-1]);
printf("%d\n%d",minv,maxv);
}
活动打卡代码
AcWing 292. 炮兵阵地
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 128;
int arr[N];
char str[10];
vector<int> legal_state;
int f[N][1<<10][1<<10];
int count(int val){
int ans=0;
while(val){
ans+=1;
val&=(val-1);
}
return ans;
}
int main()
{
int n,m;
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i ++ ){
scanf("%s",str);
for(int j=0;j<m;j++){
arr[i]<<=1;
if(str[j]=='H'){
arr[i]|=1;
}
}
//cout<<arr[i]<<endl;
}
for(int i=0;i<1<<m;i++){
if((i&(i>>1))||(i&(i>>2))){
;
}else{
legal_state.push_back(i);
}
}
for(int i=2;i<n+2;i++){
for(auto a:legal_state)for(auto b:legal_state){
if((a&b)==0){
for(auto c:legal_state){
if((a&c)==0&&(b&c)==0&&(c&arr[i-2])==0){
f[i&1][b][c]=max(f[i&1][b][c],f[(i+1)&1][a][b]+count(c));
}
}
}
}
}
int ans=0;
for(auto a:legal_state)for(auto b:legal_state){
ans=max(ans,f[(n+1)&1][a][b]);
}
printf("%d",ans);
}
活动打卡代码
AcWing 327. 玉米田
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=1<<12,M=12*12+2;
int f[14][M][N];
const int MOD=1e8;
vector<int> state;
vector<int> next_state[N];
int cnt[N];
bool check(int val){
if(val&(val>>1))return false;
else return true;
}
int mt[14];
int main()
{
int n,m;
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i ++ ){
for (int j = 0; j < m; j ++ ){
int val;
scanf("%d", &val);
mt[i]<<=1;
mt[i]|=val;
}
}
for (int i = 0; i < 1<<m; i ++ ){
if(check(i)){
state.push_back(i);
}
cnt[i]=cnt[i>>1]+(i&1);
}
for(auto s:state){
for(auto j:state){
if((s&j)==0)next_state[s].push_back(j);
}
}
f[0][0][0]=1;
for(int i=1;i<=n+1;i++){
for(int j=0;j<=m*n;j++){
for(auto s:state){
for(auto ns:next_state[s]){
if((s&mt[i-1])==s&&j-cnt[s]>=0){
f[i][j][s]+=f[i-1][j-cnt[s]][ns];
f[i][j][s]%=MOD;
}
}
}
}
}
int ans=0;
for(int i=0;i<=n*m;i++)ans=(ans+f[n+1][i][0])%MOD;
cout<<ans;
}
注意到先合并和较小的两个的结果一般较优，考虑是否能按先合并小的来求最小值，这种方法是错误的
示例：
3 2 2 3-> 3 4 3-> 7 3->10 |4+7+10=21
5 5 ->10 ->5+5+10=20
活动打卡代码
AcWing 1064. 小国王
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=1<<12;
long long f[12][102][N];
int legal[N];
int cnt[N];
vector<int> shift[N];
int c;
bool check(int val){
return !(val&(val>>1));
}
int count(int val){
int res=0;
while(val){
res++;
val&=(val-1);
}
return res;
}
int main()
{
int n,k;
cin>>n>>k;
for(int i=0;i<1<<n;i++){
if(check(i)){
legal[c++]=i;
cnt[i]=count(i);
}
}
for(int i=0;i<c;i++){
int v=legal[i];
int t=(v<<1)|v|(v>>1);
for(int j=0;j<c;j++){
int w=legal[j];
if((t&w)==0)shift[v].push_back(w);
}
}
f[0][0][0]=1;
for(int i=1;i<=n+1;i++){
for(int j=0;j<=k;j++){
for(int k=0;k<c;k++){
int s=legal[k];
for(auto t:shift[s]){
if(j-cnt[s]>=0){
f[i][j][s]+=f[i-1][j-cnt[s]][t];
}
}
}
}
}
cout<<f[n+1][k][0];
return 0;
}
