ACM杭州电大2386-2393：动态规划解题实践与分析

需积分: 9 43 浏览量更新于2024-08-02 收藏 126KB DOC 举报

本资源是一份ACM编程竞赛解题报告，针对杭州电子科技大学（Hdu）的2386-2393题目集。该报告由队伍Tzjut009在2009年5月14日提交，涉及的主题包括算法设计、动态规划和数组优化。 1. **2386. DartChallenge**: 该问题要求使用动态规划方法解决，通过定义dp[i][j]来表示在投掷第i支标枪后达到j分的目标是否可能。初始状态dp[0][0]设为1，状态转移遵循以下规则：如果dp[i-1][j]为1，则可以考虑dp[i][g+orig[j]], dp[i][g+2*orig[j]], dp[i][g+3*orig[j]]，其中g表示当前得分，orig[j]为第j支标枪的原始分数。值得注意的是，当orig[j]为最大值时，不考虑dp[i][g+2*orig[j]]的情况。 2. **2387. OnlineShopping3**: 这个题目可能是关于在线购物或资源分配的问题，但具体描述没有给出，因此无法提供详细的动态规划策略。不过，它提示了这可能是涉及多阶段决策或最优路径选择的问题。 3. **2388. PlaygroundHideout6** 至 **2393. HigherMath16**: 这一系列题目可能是不同难度级别的算法题目，包括但不限于图形操作、字符串处理、数学计算等。每个题目都需要运用不同的算法技巧和数据结构，可能涉及到递归、搜索、排序、计数等。 **代码实现部分**: 展示了C++代码片段，用于求解DartChallenge2。代码定义了一个二维数组dp，用于存储状态转移信息。首先读入测试用例数量t，然后针对每组输入（a、k、原分数数组orig），初始化dp数组，设置初始状态，对原分数数组进行排序，通过三层循环进行状态转移，并更新最高可能得分m。总结来说，这份解题报告提供了对2386号问题的完整动态规划解决方案，以及对其他几个问题类型的概括性描述。对于每个题目，理解题意、选择合适的数据结构和算法，特别是动态规划的应用，是解决问题的关键。通过阅读这份报告，参赛者可以学习如何分析问题，构建有效的状态转移方程，并优化代码以提高运行效率。

                浙江工业大学  
 }........................................................................................................................................................16
 xsort();..............................................................................................................................................16
 ysort();..............................................................................................................................................16
 /*for(i=0;i<a;i++).............................................................................................................................16
 {........................................................................................................................................................16
 for (j=0;j<b;j++){.............................................................................................................................16
 cout<<d[i][j]<<' ';.............................................................................................................................16
 }........................................................................................................................................................16
 cout<<endl;.......................................................................................................................................16
 }........................................................................................................................................................16
 cout<<endl;.......................................................................................................................................16
 */.......................................................................................................................................................16
 int fg=0;............................................................................................................................................16
 cout<<"Scenario #"<<tt-t<<':'<<endl;.............................................................................................16
 for (j=0;j<b;j++)...............................................................................................................................16
 {........................................................................................................................................................16
 for(i=0;i<a;i++){..............................................................................................................................16
 if(fg==1)...........................................................................................................................................16
 cout<<' ';...........................................................................................................................................16
 cout<<d[i][j];....................................................................................................................................16
 fg=1;.................................................................................................................................................16
 }........................................................................................................................................................16
 }........................................................................................................................................................16
 cout<<endl<<endl;...........................................................................................................................16
 }........................................................................................................................................................16
 return 0;............................................................................................................................................16
}.........................................................................................................................................................16
2388.Playground Hideout.................................................................................................................16
思路：...............................................................................................................................................16
/*只要求取地面到所有平台的最短路径，然后在这些最短路径中找出最大的一条就可以了。
...........................................................................................................................................................16
采用邻接表来储存节点计算最短路径，以节省内存开支。*/...................................................17
代码：...............................................................................................................................................17
#include<iostream>...........................................................................................................................17
#include<cmath>...............................................................................................................................17
#include <vector>..............................................................................................................................17
#include <algorithm>........................................................................................................................17
#include <fstream>............................................................................................................................17
using namespace std;.........................................................................................................................17
#define MAXN 10007.......................................................................................................................17
#define inf 1000000000....................................................................................................................17
typedef int elem_t;.............................................................................................................................17
struct edge_t{.....................................................................................................................................17
Tzjut009 第 5 页 2021-8-5

                浙江工业大学  
 int from,to;........................................................................................................................................17
 elem_t len;........................................................................................................................................17
 edge_t* next;....................................................................................................................................17
 edge_t* end;.....................................................................................................................................17
};........................................................................................................................................................17
#define _cp(a,b) ((a)<(b))..................................................................................................................17
struct heap{........................................................................................................................................17
 elem_t h[MAXN+1];........................................................................................................................17
 int ind[MAXN+1],map[MAXN+1],n,p,c;.......................................................................................17
 void init(){n=0;}...............................................................................................................................17
 void ins(int i,elem_t e){...................................................................................................................17
 for (p=++n;p>1&&_cp(e,h[p>>1]);h[map[ind[p]=ind[p>>1]]=p]=h[p>>1],p>>=1);....................17
 h[map[ind[p]=i]=p]=e;.....................................................................................................................17
 }........................................................................................................................................................17
 int del(int i,elem_t& e){...................................................................................................................17
 i=map[i];if (i<1||i>n) return 0;.........................................................................................................17
 for (e=h[p=i];p>1;h[map[ind[p]=ind[p>>1]]=p]=h[p>>1],p>>=1);...............................................17
  for   (c=2;c<n&&_cp(h[c+=(c<n-
1&&_cp(h[c+1],h[c]))],h[n]);h[map[ind[p]=ind[c]]=p]=h[c],p=c,c<<=1);.....................................17
 h[map[ind[p]=ind[n]]=p]=h[n];n--;return 1;....................................................................................17
 }........................................................................................................................................................17
 int delmin(int& i,elem_t& e){..........................................................................................................17
 if (n<1) return 0;i=ind[1];.................................................................................................................17
  for   (e=h[p=1],c=2;c<n&&_cp(h[c+=(c<n-
1&&_cp(h[c+1],h[c]))],h[n]);h[map[ind[p]=ind[c]]=p]=h[c],p=c,c<<=1);.....................................17
 h[map[ind[p]=ind[n]]=p]=h[n];n--;return 1;....................................................................................17
 }........................................................................................................................................................17
};........................................................................................................................................................18
void dijkstra(int n,edge_t* list[],int s,elem_t* min,int* pre){..........................................................18
 heap h;..............................................................................................................................................18
 edge_t* t;elem_t e;...........................................................................................................................18
 int v[MAXN],i;.................................................................................................................................18
 for (h.init(),i=0;i<n;i++)...................................................................................................................18
 min[i]=((i==s)?0:inf),v[i]=0,pre[i]=-1,h.ins(i,min[i]);....................................................................18
 while (h.delmin(i,e)).........................................................................................................................18
 for (v[i]=1,t=list[i];t->next != NULL ;t=t->next)............................................................................18
 if (!v[t->to]&&min[i]+t->len<min[t->to]).......................................................................................18
 pre[t->to]=i,h.del(t->to,e),min[t->to]=e=min[i]+t->len,h.ins(t->to,e);...........................................18
}.........................................................................................................................................................18
int main()...........................................................................................................................................18
{.........................................................................................................................................................18
 int cases,platformnum, connum;......................................................................................................18
 int i,j;.................................................................................................................................................18
Tzjut009 第 6 页 2021-8-5

剩余25页未读，继续阅读

gzq_pym

粉丝: 2
资源: 4

ACM杭州电大2386-2393：动态规划解题实践与分析

杭电ACM -ppt

杭电ACM-HDUOJ 1001 SUM problem

acm7060f-301T50

acm.hi-54.com答案

int ACM(int M, int N) { if (M==0) return N+1; else if (N==0) return ACM(M-1,1); else return ACM(M-1,ACM(M,N-1)); } 调用 cout<<ACM(2,2) 上述代码结果是多少

ACM-ICPC真题

ACM-ICPC模板整理

acm-icpc国际大学生程序设计竞赛 知识与入门

题目描述：编写一函数实现下列ackman函数，其中m，n为正整数 acm(m,n)= ⎩ ⎪ ⎪ ⎨ ⎪ ⎪ ⎧ ​ n+1 acm(m−1,1) acm(m−1,acm(m,n−1)) ​ if m=0,n>0 if n=0,m>0 if n>0,m>0 ​

ACM-ICPC赛题

最新资源

acm-icpc国际大学生程序设计竞赛知识与入门

题目描述：编写一函数实现下列ackman函数，其中m，n为正整数 acm(m,n)= ⎩ ⎪ ⎪ ⎨ ⎪ ⎪ ⎧ n+1 acm(m−1,1) acm(m−1,acm(m,n−1)) if m=0,n>0 if n=0,m>0 if n>0,m>0