动态规划
- 动态规划适用于子问题不是独立的情况。也就 是子问题包含公共的子子问题（如fibnacci数列问题求解第 n项时，需要调用第n-1和第n-2项，而求第n-1项时又要调 用第n-2项，此处公共子问题就是第n-2项）。在这种情况 下，采用传统的递归分治法会做很多不必要的冗余计算， 即重复地求解公共的子问题（如F[i]），所以效率比较低
这个主要是动态转移方程，随便挑几道例题：
1.数字三角形
#include
using namespace std;
int a[1145][1145],f[1145][1145];
int n;
int main()
{
cin>>n;
for(int i=1;ia[i][j];
f[n][j]=a[n][j];
}
}
for(int i=n-1;i>=1;i--)
{
for(int j=i;j>=1;j--)
{
f[i][j]=a[i][j]+max(f[i+1][j],f[i+1][j+1]);
}
}
cout<<f[1][1];
}
2.拦截导弹（mis)
#include
using namespace std;
int n,a[110],dp[110],b[110];
int main()
{
freopen("mis.in","r",stdin);
freopen("mis.out","w",stdout);
cin>>n;
for(int i=1;i>a[i];
for(int i=n;i>=1;i--)
{
dp[i]=1;
for(int j=i+1;j<=n;j++)
if(a[j]<=a[i]) dp[i]=max(dp[i],dp[j]+1);
}
int l=0;
for(int i=1;i<=n;i++) l=max(l,dp[i]);
cout<<l<<endl;
l=1;
b[1]=a[1];
for(int i=1;i<=n;i++)
{
int k=1;
if(b[l]<a[i]) b[++l]=a[i];
while(k<=l && b[k]<a[i]) k++;
b[k]=a[i];
}
cout<<l<<endl;
return 0;
}
2.ship(航线)
这题和友好城市代码基本一致，只要把比较多加个等于，
并且把输入x和y删掉，就可以了
#include
using namespace std;
int x,y,n,f[5001];
struct node
{
int beg;
int en;
};
node a[5001];
bool cmp(node x,node y)
{
return x.beg>x>>y>>n;
for(int i=1;i>a[i].beg>>a[i].en;
sort(a+1,a+n+1,cmp);
//for(int i=1;i<=n;i++) cout<<a[i].beg<<" "<<a[i].en<<endl;
int maxn=0;
for(int i=1;i<=n;i++)
{
f[i]=1;
for(int j=1;j<i;j++)
{
if(a[j].en<a[i].en) f[i]=max(f[i],f[j]+1);
}
maxn=max(maxn,f[i]);
}
cout<<maxn;
return 0;
}
DP模板题
- 最长不下降子序列
#include
using namespace std;
int n;
int a[250],dp[250];
int main()
{
cin>>n;
for(int i=1;i>a[i];
for(int i=1;i<=n;i++)
{
dp[i]=1;
for(int j=1;j<i;j++)
{
if(a[j]<=a[i]) dp[i]=max(dp[i],dp[j]+1);
}
}
int maxn=0;
for(int i=1;i<=n;i++) maxn=max(maxn,dp[i]);
cout<<"Max="<<maxn<<endl;
return 0;
}
- 最长公共子序列
#include
using namespace std;
string a,b;
int dp[5010][5010];
int main()
{
cin>>a>>b;
int len1=a.size(),len2=b.size();
for(int i=1;i<=len1;i++)
{
for(int j=1;j<=len2;j++)
{
dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
if(a[i-1]==b[j-1]) dp[i][j]=max(dp[i][j],dp[i-1][j-1]+1);
}
}
cout<<dp[len1][len2]<<endl;
return 0;
}
- 最长上升子序列
这个思路就和最长不下降子序列差不多
把a[j]<=a[i] 的等于号删了就可以了
代码就不再此展示
总而言之，DP是个很sb有用的东西
2.比赛
今天的比赛十分的一言难尽
从1：30~4：30都在打题（真无聊啊
分数：200/400；
第一题10分，暴力才10分？（我很疑惑
第二题90分，忘记特判n=1的时候了，只拿了90分
第三题，一道搜索题，我用的bfs，考试的时候样例都没对
但是提交上去AC了（离谱
其实思路和标程一模一样，就只有边界有点小错误，改完AC
（很难想象，我和标程除了边界不一样，其他就只有我是模拟队列，它是真队列了）（考试的时候脑子果然好使一点点）
我认为还有一个奇怪的原因：
1.cakeii
题解：
前缀和
用l[i]记录前缀和余数为i的最左位置
用r[i]记录前缀和余数为i的最右位置
那最后答案就是max(r[i] – l[i])
#include
#define int long long
using namespace std;
int n,a[50005];
int sum,k,l[8],r[8];
signed main()
{
freopen("cakeii.in","r",stdin);
freopen("cakeii.out","w",stdout);
cin>>n;
l[0]=0;r[0]=0;
for(int i=1;ia[i];
sum+=a[i];
k=sum%7;
if(ir[k]) r[k]=i;
}
int maxn=0;
for(int i=0;i<7;i++)
{
if(l[i]<r[i]) maxn=max(maxn,r[i]-l[i]);
}
cout<<maxn<<endl;
return 0;
}
2.stone
就是忘记n=1的情况了（真服了
#include
using namespace std;
int read()
{
int Ca=0;char Cr=' ';int Cf=1;
while(Cr'9'){Cr=getchar();if(Cr=='-'){Cf=-1;}}
while(Cr>='0' && Cr<='9'){Ca=Ca*10+Cr-48;Cr=getchar();}
return Ca*Cf;
}
long long n,c;
int main()
{
freopen("stone.in","r",stdin);
freopen("stone.out","w",stdout);
n=read();
if(n==1)
{
cout<<"1";
return 0;
}
if(n==2 || n==3) {printf("2");return 0;}
if(n%2!=0) n++;
c=1;
while(n)
{
c++;
n/=2;
if(n==1) n=0;
}
cout<<c;
return 0;
}
3.arena
最神奇的一题，不太理解没过样例怎么AC
只能说明数据太水
- 原AC代码（很神奇的错了样例
#include
using namespace std;
int n,m,sum_o,sum_v,o,v,f;
char a[255][255];
int xi[5]={0,1,-1,0,0};
int yi[5]={0,0,0,1,-1};
void bfs(int x,int y)
{
int new_x,new_y,tail,front;
int q[63000][3];
o=0;v=0;f=0;
if(a[x][y]=='o') o++;
else if(a[x][y]=='v') v++;
a[x][y]='#';front=1;tail=1;
q[1][1]=x;q[1][2]=y;
do
{
for(int i=1;i1 && new_x1 && new_y<m && a[new_x][new_y]!='#')
{
tail++;
q[tail][1]=new_x;
q[tail][2]=new_y;
if(a[new_x][new_y]=='o') o++;
else if(a[new_x][new_y]=='v') v++;
a[new_x][new_y]='#';
}
}
front++;
}while(front<=tail);
// cout<<o<<" "<<v<v) v=0;
else o=0;
}
if(f==0)
{
sum_o+=o;
sum_v+=v;
}
//cout<<sum_o<<" "<<sum_vn>>m;
for(int i=1;ia[i][j];
}
for(int i=2;i<n;i++)
{
for(int j=2;j<m;j++)
{
if(a[i][j]!='#')
{
if(i!=2 && j!=2 && i!=n-1 && j!=n-1) bfs(i,j);
else if(i==2 && a[i-1][j]=='#') bfs(i,j);
else if(j==2 && a[i][j-1]=='#') bfs(i,j);
else if(i==n-1 && a[i+1][j]=='#') bfs(i,j);
else if(j==n-1 && a[i][j+1]=='#') bfs(i,j);
}
}
}
cout<<sum_o<<" "<<sum_v;
return 0;
}
- 改后（其实就没啥区别，有区别还是因为我特判改的）
#include
using namespace std;
int n,m,sum_o,sum_v,o,v,f;
char a[255][255];
int xi[5]={0,1,-1,0,0};
int yi[5]={0,0,0,1,-1};
void bfs(int x,int y)
{
int new_x,new_y,tail,front;
int q[63000][3];
o=0;v=0;f=0;
if(a[x][y]=='o') o++;
else if(a[x][y]=='v') v++;
a[x][y]='#';front=1;tail=1;
q[1][1]=x;q[1][2]=y;
do
{
for(int i=1;i=1 && new_x=1 && new_y<=m && a[new_x][new_y]!='#')
{
tail++;
q[tail][1]=new_x;
q[tail][2]=new_y;
if(a[new_x][new_y]=='o') o++;
else if(a[new_x][new_y]=='v') v++;
a[new_x][new_y]='#';
}
}
front++;
}while(front<=tail);
// cout<<o<<" "<<v<v) sum_o+=o;
else sum_v+=v;
//cout<<sum_o<<" "<<sum_vn>>m;
for(int i=1;ia[i][j];
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(a[i][j]!='#')
{
bfs(i,j);
}
}
}
cout<<sum_o<<" "<<sum_v;
return 0;
}
4.fruit
#include
#define int long long
using namespace std;
const int N=1e6+10;
int n,a[N];
int dp[N][4][2];
signed main()
{
freopen("fruit.in","r",stdin);
freopen("fruit.out","w",stdout);
memset(dp,-0x3f3f3f3f,sizeof dp);
cin>>n;
for(int i=1;i>a[i];
dp[0][0][0]=0;
for(int i=1;i<=n;i++)
{
for(int j=0;j=1)
dp[i][j][1]=max(dp[i][j][1],max(dp[i-1][j-1][0],dp[i-1][j-1][1])+a[i]);
}
}
int sum=max(dp[n][3][0],dp[n][3][1]);
cout<<sum<<endl;
return 0;
}