NOIP2006 提高组 复赛 energy 能量项链
//觉得想得蛮好，提交，测试点1,4,8,9,10 WA
//提供一组测试数据
//4
//3 2 1 4
//输出
//80
//for(i=1;i+k<=2*n-1;i++)//此处写成for(i=1;i<=n;i++),查了好长时间
//for(i=1;i<=n;i++)只算了1,2,...,n为起始位置的情况
//n+1,n+2,...为起始位置的情况没有计算。 2018-11-1 18:16
//修改，提交AC。2018-11-1 18:07
#include <stdio.h>
#include <string.h>
#define maxn 220
int f[maxn][maxn],a[maxn];
int max(int a,int b){
return a>b?a:b;
}
int main(){
int n,i,j,k,ans=0;
scanf("%d",&n);
for(i=1;i<=n;i++){
scanf("%d",&a[i]);
a[n+i]=a[i];
}
memset(f,0,sizeof(f));
//忘记初始化了
for(k=1;k<=n-1;k++)//2个 3个 n个
for(i=1;i+k<=2*n-1;i++)//此处写成for(i=1;i<=n;i++),查了好长时间//起始序号
for(j=i;j<i+k;j++)//剖开位置
f[i][i+k]=max(f[i][i+k],f[i][j]+f[j+1][i+k]+a[i]*a[j+1]*a[i+k+1]);
for(i=1;i<=n;i++)
if(ans<f[i][i+n-1])
ans=f[i][i+n-1];
printf("%d\n",ans);
return 0;
}
1.读完题目，挺简单的，开个结构体，存储节点的头尾信息。
2.读取数据，记录头尾信息。
3.按顺序进行珠子能量合并，找出最大能量值。
4.提交10分，反复读题，觉得没问题，又觉得有问题，想了想，如果数据给定比较合适，珠子的合并顺序，可以不依照输入顺序进行合并，那该怎么处理呢，好像以目前的知识无能为力啊。
5.上网搜索，果然，说是动态规划问题，那就从头学吧。
6.学习http://wenku.baidu.com/link?url=UDL6fMzYuoXAl35TVnazjoGCIzZ3jUOtITvlitwybrhYNczdnsHMmYFJXb1e1ilxRFbfBdTYEqpcDjB3-gQ0Pf6nF_wItx9JyWKnctAAYsO动态规划：从新手到专家http://blog.csdn.net/hzj379805931/article/details/51050741
附上数硬币对应的代码，根据文中伪代码，第一次用动态规划思想编写程序，很是高兴：
//dp count_coin 非递归
#include <stdio.h>
int v[3]={1,3,5};//币值种类
int min[1000000];
const int inf=999999;
int main(){
int s;//总金额
int i,j;
scanf("%d",&s);//输入总金额
min[0]=0;
for(i=1;i<=s;i++)
min[i]=inf;
for(i=1;i<=s;i++)
for(j=0;j<3;j++)
if(v[j]<=i&&min[i-v[j]]+1<min[i])
min[i]=min[i-v[j]]+1;
printf("min[%d]=%d\n",s,min[s]);//输出构成总金额s的最少硬币个数
}
//dp count_coin2 递归
#include <stdio.h>
int v[3]={1,3,5};
int fun(int s){
int i;
int min=99999;
if(s==0)
return 0;
for(i=0;i<3;i++)
if(s>=v[i]&&fun(s-v[i])+1<min)
min=fun(s-v[i])+1;
return min;
}
int main(){
int s;
scanf("%d",&s);
printf("%d\n",fun(s));
return 0;
}
附上最长非降子序列的长度代码（我们定义d(i)，表示前i个数中以A[i]结尾的最长非降子序列的长度。）
//longest increasing subsqeuence 非递归
#include <stdio.h>
int main(){
int a[]={5,3,4,8,6,7};
int n=6;
int i,j;
int d[6];
int maxLen;
for(i=0;i<n;i++){
maxLen=1;
for(j=0;j<i;j++){
d[i]=maxLen;
if(a[j]<=a[i]&&d[j]+1>d[i])
d[i]=d[j]+1;
if(d[i]>maxLen)
maxLen=d[i];
}
d[i]=maxLen;
}
printf("%d\n",d[5]);
return 0;
}
//longest increasing subsequence 递归
#include <stdio.h>
int a[]={5,3,4,8,6,7};
int lis(int n){
int i,j;
int maxLen;
if(n==0)
return 1;
maxLen=1;
for(i=0;i<n;i++)
if(a[i]<=a[n]&&lis(i)+1>maxLen)
maxLen=lis(i)+1;
return maxLen;
}
int main(){
printf("%d\n",lis(6-1));
}
找到一篇好文，http://blog.csdn.net/qq632544991p/article/details/52434951能将上述内容补齐
松鼠吃苹果，介绍得不错，但输出结果有误。又找了一个http://www.cnblogs.com/zhezh/p/3773284.html
附上苹果代码
//apple 非递归
#include <stdio.h>
int a[100][100];
int s[100][100];
int main(){
int i,j;
int row,col;
scanf("%d%d",&row,&col);
for(i=0;i<row;i++)
for(j=0;j<col;j++)
scanf("%d",&a[i][j]);
//初始化，第一行，第一列
s[0][0]=a[0][0];
for(j=1;j<col;j++)//第一行
s[0][j]=s[0][j-1]+a[0][j];
for(i=1;i<row;i++)//第一列
s[i][0]=s[i-1][0]+a[i][0];
for(i=1;i<row;i++)
for(j=1;j<col;j++)
if(s[i][j-1]>s[i-1][j])
s[i][j]=s[i][j-1]+a[i][j];
else
s[i][j]=s[i-1][j]+a[i][j];
for(i=0;i<row;i++){
for(j=0;j<col;j++)
printf("%d\t",s[i][j]);
printf("\n");
}
return 0;
}
输入数据：
3 3
1 2 3
4 5 6
7 8 9
输出数据：
1 3 6
5 10 16
12 20 29
//apple 递归
#include <stdio.h>
int a[100][100];
int s[100][100];
int makes(int r,int c){
if(r==0&&c==0)//第一个数据
s[r][c]=a[r][c];
else if(r==0)//第一列
s[r][c]=makes(r,c-1)+a[r][c];
else if(c==0)//第一行
s[r][c]=makes(r-1,c)+a[r][c];
else{
if(makes(r,c-1)>makes(r-1,c))
s[r][c]=makes(r,c-1)+a[r][c];
else
s[r][c]=makes(r-1,c)+a[r][c];
}
return s[r][c];
}
int main(){
int i,j;
int row,col;
scanf("%d%d",&row,&col);
for(i=0;i<row;i++)
for(j=0;j<col;j++)
scanf("%d",&a[i][j]);
s[row-1][col-1]=makes(row-1,col-1);
for(i=0;i<row;i++){
for(j=0;j<col;j++)
printf("%d\t",s[i][j]);
printf("\n");
}
return 0;
}
能量项链，这几篇文章介绍得不错：
http://blog.sina.com.cn/s/blog_4c396f4301000bol.html
http://blog.csdn.net/a351357741/article/details/6493945
http://blog.sina.com.cn/s/blog_963453200101ketm.html
http://www.cnblogs.com/CYWer/p/4778720.html
着重http://blog.sina.com.cn/s/blog_963453200101ketm.html，可惜程序看不懂，怎么办，祭出跟踪大法，弄明白了，
第一重循环确定，聚合能量珠子总个数
第二重循环确定，第一个聚合珠子的起点位置
第三重循环确定，在起点珠子与终点珠子之间剖开位置。
开始编码，希望能成功。
附上AC代码，编译环境Dev-C++4.9.9.2
//2006 energy3
#include <stdio.h>
#include <string.h>
int e[200+20][200+20];
int a[200+20];
int my_max(int a,int b){
if(a>=b)
return a;
else
return b;
}
int main(){
int n;
int i,j,k;
int t,max_e;
scanf("%d",&n);
for(i=1;i<=n;i++){
scanf("%d",&a[i]);
a[n+i]=a[i];
}
memset(e,0,sizeof(e));//别忘了初始化，e[i][i]=0;
for(j=1;j<=n-1;j++){//聚合珠子个数j+1
for(i=1;i+j<=2*n-1;i++){//聚合珠子起点序号
t=0;
for(k=0;k<=j-1;k++){//聚合珠子剖开位置
t=my_max(t,e[i][i+k]+e[i+k+1][i+j]+a[i]*a[i+k+1]*a[i+j+1]);//a[i]容易写成a[i+k]
}
e[i][i+j]=t;//此处容易犯错，e[i][j];
}
}
max_e=0;
for(i=1;i<=n;i++)
max_e=my_max(max_e,e[i][i+n-1]);
printf("%d\n",max_e);
return 0;
}
很明显该题的动态归化难在写代码，不过认清珠子聚合至少两个，至多n个，作为第一重循环，此题就不难了。
2017-1-5 20:04
附上10分代码，编译环境Dev-C++4.9.9.2
//2006 energy 能量项链
#include <stdio.h>
struct node{
int head;
int tail;
}d[100+10];
int main(){
int i,j;
int n;
int v;
int max=-1;
int e;
int newhead,newtail;
scanf("%d",&n);
for(i=0;i<n;i++){
scanf("%d",&v);
d[i].head=v;
}
d[n-1].tail=d[0].head;
for(i=0;i<n-1;i++)
d[i].tail=d[i+1].head;
for(i=0;i<n;i++){
e=0;
newhead=d[i].head;
newtail=d[i].tail;
for(j=i+1;j<n+i;j++){
e+=newhead*newtail*d[j%n].tail;
newtail=d[j%n].tail;
}
if(max<e)
max=e;
}
printf("%d\n",max);
return 0;
}
![noip2013day1第三题 货车运输LCA+并查集[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)