首页 > 代码库 > pku ppt some problem
pku ppt some problem
The Triangle http://poj.org/problem?id=1163
暴力dfs的话，每个节点有两条路可以走，那么n个节点复杂度就是2^n n=100 超时 dp来做 就优化成 n^2
记忆化搜索，就能优化成n^2 因为一个点最多算一次，以后会直接返回dp i j 。 dp i j 表示这个位置能获得最大值。最后一行就是a i j ，其他行都可以由下面两条路取最大值。
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #define mt(a,b) memset(a,b,sizeof(a)) 5 using namespace std; 6 const int M=128; 7 int n,a[M][M],dp[M][M]; 8 int dfs(int i,int j){ 9 if(~dp[i][j]) return dp[i][j];10 if(i==n) dp[i][j]=a[i][j];11 else dp[i][j]=max(dfs(i+1,j),dfs(i+1,j+1))+a[i][j];12 return dp[i][j];13 }14 int main(){15 while(~scanf("%d",&n)){16 for(int i=1;i<=n;i++){17 for(int j=1;j<=i;j++){18 scanf("%d",&a[i][j]);19 }20 }21 mt(dp,-1);22 printf("%d\n",dfs(1,1));23 }24 return 0;25 }
自底向上的推法，那dp i j 就表示i j 这个位置能获得的最大值， 然后dp i j 可以推向两个状态，分别是 dp i-1 j 和 dp i-1 j-1. 这是用当前状态去推能到达的所有状态的写法。
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #define mt(a,b) memset(a,b,sizeof(a)) 5 using namespace std; 6 const int M=128; 7 int a[M][M],dp[M][M]; 8 int main(){ 9 int n;10 while(~scanf("%d",&n)){11 for(int i=1;i<=n;i++){12 for(int j=1;j<=i;j++){13 scanf("%d",&a[i][j]);14 }15 }16 mt(dp,0);17 for(int i=n+1;i>=1;i--){18 for(int j=1;j<=n;j++){19 dp[i-1][j]=max(dp[i-1][j],dp[i][j]+a[i-1][j]);20 dp[i-1][j-1]=max(dp[i-1][j-1],dp[i][j]+a[i-1][j-1]);21 }22 }23 printf("%d\n",dp[1][1]);24 }25 return 0;26 }
这是用所有能到达的状态推当前状态的写法，并且空间优化了一下，省去了输入的数组。
1 #include<cstdio> 2 #include<algorithm> 3 using namespace std; 4 const int M=128; 5 int dp[M][M]; 6 int main(){ 7 int n; 8 while(~scanf("%d",&n)){ 9 for(int i=1;i<=n;i++){10 for(int j=1;j<=i;j++){11 scanf("%d",&dp[i][j]);12 }13 }14 for(int i=n-1;i>=1;i--){15 for(int j=1;j<=i;j++){16 dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+dp[i][j];17 }18 }19 printf("%d\n",dp[1][1]);20 }21 return 0;22 }
最长上升子序列 http://bailian.openjudge.cn/practice/2757/
end
pku ppt some problem
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。