第一篇：动态规划总结经典题目(经典中的经典)
动态规划总结——经典问题总结
本文着重讨论状态是如何表示，以及方程是怎样表示的。当然，还附上关键的，有可能作为模板的代码段。但有的代码的实现是优化版的。
经典问题总结
最长上升子序列（LIS）
问题描述如下:
设L=
有了以上的思想，DP方程就呼之欲出了（这里是顺序推的，不是逆序的）： DP[I]=MAX（1,DP[J]+1）J=0,1,...,I-1
但这样的想法实现起来是）O(n^2)的。本题还有更好的解法，就是O(n*logn)。利用了长升子序列的性质来优化，以下是优化版的代码：
//最长不降子序 const int SIZE=500001;int data[SIZE];int dp[SIZE];
//返回值是最长不降子序列的最大长度,复杂度O(N*logN)
int LCS(int n){ //N是DATA数组的长度,下标从1开始 int len(1),low,high,mid,i;
dp[1]=data[1];for(i=1;i<=n;++i){ low=1;high=len;
while(low<=high){ //二分 mid=(low+high)/2;if(data[i]>dp[mid]){ low=mid+1;} else {
high=mid-1;} }
dp[low]=data[i];if(low>len){ ++len;} }
return len;}
最长公共子序列（LCS）
给出两个字符串a, b，求它们的最长、连续的公共字串。
这很容易就想到以DP[I][J]表示A串匹配到I，B串匹配到J时的最大长度。则：
0 I==0 || J==0
DP[I][J]=DP[I-1][J-1]+ 1 A[I]==B[J] MAX（DP[I-1][J]，DP[I][J-1]）不是以上情况
但这样实现起来的空间复杂度为O(n^2)，而上面的方程只与第I-1行有关，所以可以用两个一维数组来代替。以下是代码：
//最长公共子序列
const int SIZE=1001;
int dp[2][SIZE];//两个一维数组
//输入两个字符串，返回最大的长度
int LCS(const string& a,const string& b){ int i,j,flag;
memset(dp,0,sizeof(dp));
flag=1;
for(i=1;i<=a.size();++i){ for(j=1;j<=b.size();++j){
if(a[i-1]==b[j-1])dp[flag][j]=dp[1-flag][j-1]+1;else dp[flag][j]=MAX(dp[flag][j-1],dp[1-flag][j]);}
flag=1-flag;}
return dp[1-flag][b.size()];}
01背包
有N件物品和一个容量为V的背包。第i件物品的大小是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。
用DP[I][J] 表示前I件物品放入一个容量为J的背包可以获得的最大价值。则 DP[I][J]= DP[I-1][J] ,J MAX（DP[I-1][J]，DP[I-1][J-C[I]]+W[I]）, J>=C[I] 这样实现的空间复杂度为O(VN)，实际上可以优化到O（V）。以下是代码： const int MAXW=13000;//最大重量 const int MAXN=3450;//最大物品数量 int c[MAXN];//物品的存放要从下标1开始 int w[MAXN];//物品的存放要从下标1开始 int dp[MAXW]; //不需要将背包装满，则将DP数组全部初始化为0 //要将背包装满，则初始化为DP[0]=0，DP[1]…DP[V]=-1(即非法状态)int Packet(int n,int v){ int i,j; memset(dp,0,sizeof(dp));for(i=1;i<=n;++i){ for(j=v;j>=c[i];--j){ //这里是倒序，别弄错了 dp[j]=MAX(dp[j],dp[j-c[i]]+w[i]);} } return dp[v];} 完全背包问题 有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。 很容易可以得到这种状态表示：用DP[I][J] 表示前I件物品放入一个容量为J的背包可以获得的最大价值。则 DP[I][J]=MAX（DP[I-1][J]，DP[I-1][J-K*C[I]]+K*W[I]）0<=K*C[I]<=J 这样的复杂度是O(V*Σ(V/c[i])) 有更好的做法，那就是利用01背包的优化原理。在优化的代码中，之所以第二重循环是倒序，是为了防止重复拿，那么只要将其变为顺序即可以重复取。代码就不给了。 多重背包问题 有N种物品和一个容量为V的背包。第i种物品最多有n[i]件可用，每件费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。 这题仍然可以用到上一题的思想，DP表示状态与上面的相同。方程为： DP[I][J]=MAX（DP[I-1][J]，DP[I-1][J-K*C[I]]+K*W[I]） 不同的是K的范围，0<=K<=N[I] && 0<=K*C[I]<=J 这样的复杂度为O(V*Σn[i])。有更好的想法就是先用二进制来划分。将第i种物品分成若干件物品，其中每件物品有一个系数，这件物品的费用和价值均是原来的费用和价值乘以这个系数。使这些系数分别为1,2,4,...,2^(k-1),n[i]-2^k+1，且k是满足n[i]-2^k+1>0的最大整数。然后用01背包做，这样的复杂度为O(V*Σlog n[i])。关键代码： const int SIZE=1001;int dp[SIZE]; int num[SIZE],c[SIZE],w[SIZE];//num[i]是I物品的件数,C[I]是费用，W[I]是价值 int MultiPack(int n,int v){ //存入参数，N是物品种类数，V是背包容量 int i,j,k; memset(dp,0,sizeof(dp)); for(i=1;i<=n;++i){ //存放物品的数组下标从1开始 if(c[i]*num[i]>=v){ for(j=c[i];j<=v;++j){ dp[j]=MAX(dp[j],dp[j-c[i]]+w[i]);} } else { //使用二进制划分 k=1; while(k dp[j]=MAX(dp[j],dp[j-k*c[i]]+k*w[i]);} num[i]-=k;k*=2;} for(j=v;j>=num[i]*c[i];--j){ dp[j]=MAX(dp[j],dp[j-num[i]*c[i]]+num[i]*w[i]);} } } return dp[v];} 状态表示总结 一维的状态表示 DP的表示形式通常为：DP[I]表示取到第I个/种物品时的最优值。DP方程的形式：DP[I]=MAX（DP[I]，DP[J]+P[I]）其中0<=J 有一些题可能要将一些额外的东西也认为是物品。如HDU2059龟兔赛跑这题，需要将开始点和终点也认为是加油站，然后才以DP[I]表示到第I个加油站并加满油的最短时间。 有一些题可以将看似二维的情况转化为一维的情况来做。如HDU 1081这题。大意是给出一个含有正数和负数的N阶矩阵，求一个子矩阵使得子矩阵内所有数的和最大。这样的题可以将几行合并为一行做。即枚举就将第I行到第J行合并为一行，然后再用DP[K]=MAX（DP[K-1]，0）+ARR[K]，K是表示第K列。 有一些题是DP与暴力相结合，如POJ 3267 The Cow Lexicon这题。大意是给出一个长的字符串，还有若干个短的字符串，问长字符中至少要删除几个字符才能使得长字符串中的子字符串都与某个短字符串相对应。dp[i]表示从I到LEN-1需要删除的最少字符串数，则dp[i]=min(dp[i+1]+1，dp[k]+del)其中dp[i+1]+1是没有找到匹配的情况，dp[k]+del是有匹配的情况,K表示从I开始匹配,到匹配完后的最后一个字符的位置,DEL表示在匹配过程中要删除的字符数。由于方程的特点，要从最后一个字符向第一个字符推去。中间要删除的字符数用暴力找出。 有一些题用DP来枚举全部的范围，如POJ 1925 Spiderman这题。用DP[I]表示到达这个位置的最小跳数。其中DP数组为dp[1000005]，这是可能跳到的全部范围。 二维状态表示 通常是用来处理两种事物。DP[I][J]通常表示A的前I个和B的前J个XX的最优值。 DP方程之一：DP[I][J]=MAX（DP[I-1][J-1]+P[XX]，DP[I][J-1]+P[YY]，DP[I-1][J]+P[ZZ]）这里的XX，YY，ZZ是表示某某状态得到的结果。 DP方程之二：DP[I][J]=MAX（DP[I][J]，DP[I-1][K]+P[I][J]），其中0<=K 对第三种DP方程举个例：POJ 3280 Cheapest Palindrome这题。大意是给出一个字符串，你可在任意位置增加或删除字符，每增加或删除一个字符都有一个对应的代价，求将其变为回文串的最小代价。以dp[i][j]表示从i到j要变成回文字符串的最小代价，则 dp[i][j] = min{ dp[i+1][j] + {去掉X的代价}，dp[i+1][j] + {加上X的代价}，dp[i][j-1]+ {去掉Y的代价}，dp[i][j-1] +{加上Y的代价}}； 算DP[I][J]时，要知道DP[I+1][J]的值，对于这类DP其实现方法如下所示： for(t=1;t 有时可以将DP与HASH相结合。如：POJ 1054 The Troublesome Frog这题。大意是在一个坐标系中给出N个点，求找出以哪两点作一条直线经过的点数最多。以DP[I][J]表示过第J点和第I点的直线一共经过的点数。DP[I][J]=（DP[J][INDEX]+1，-INF），先算出INDEX这点的坐标，然后用哈希查找，如果找到，则执行DP[J][INDEX]+1，如果找不到则用-INF表示不存在。 对于整除类型的题，如果要用DP做，那么其中有一维通常是佘数。如：POJ 1745Divisibility这题，dp[i][j]表示对前I个数进行了处理,余数为J的情况 带偏移的状态表示 DP的表示形式通常为：DP[I][J]表示到第I个XX时，YY与ZZ之差为J时的最优值。例如：POJ 1837这题。 题目大意：给出天平c个挂钩的位置,然后给出g个物品的质量,将物品挂在天平上,问使天平平衡的方法有几种。 思想：用l[i]表示第i个点的x坐标值，用w[i]表示第i个砝码的重量，用dp[i][j]表示加了i个砝码，两边力矩之差为j的可能方法数，则本题只要计算出dp[i][0]，即最终力矩差为0的方法数即可。由于质量差可能为负，这里加上一个偏移量，考虑原题的数据可知，要想平衡，则一边力矩至多为15*25*10=3750，故每个j加上3750。状态转移方程：dp[i+1][k+w[i]*l[j]]+= dp[i][k]，i=0~g，j=0~c，k=0~7500。输出结果：dp[w][3750] 动态规划变态总结 by zeus 1：Pku acm 1163 the Triangle 2：Pku acm 1953 World Cup Noise //说白了就是斐波那切数列 3：Pku acm 1458 Common Subsequence Lcs 4：Pku acm 2250 Compromise记录路径的lcs 5：Pku acm 1159 Palindrome 回文串 6：Pku acm 1080 Humman Gene Function 7：Pku acm 2192 Zipper 判断2个字符串能否组成1个字符串 8：Pku acm 3356 AGTC 一个字符串到另一个的最小步骤 9：Pku acm 1887 Testing the CATCHER最长下降子序列 10：Pku acm 2533 Longest Ordered Subsequence最长上升子序列 11：Pku acm 1631 Bridging signals最长上升子序列的加强版….二分法 12：Pku acm 1157 LITTLE SHOP OF FLOWERS 13：Pku acm 1088 滑雪 14：Pku 1050 To the Max 15：Pku 1050 To the Max最大线段和的加强板…..二维的 16：Pku 1014 dividing 17: Pku acm 1160 post office 18: pku acm 1015 Jury Compromise 19: hdoj 2546饭卡 20:pku 1837 Balance 21: pku 3267 The Cow Lexicon 22:Pku 1742 Coins //走塔....经典的dp #include “iostream” using namespace std;int max(int a,int b){ return a>b?a:b;} int main(){ int n,i,j; int a[100][100]; int f[100];while(scanf(“%d”,&n)>0){ for(i=0;i for(j=0;j<=i;j++) { scanf(“%d”,&a[i][j]); if(i==n-1) f[j]=a[i][j]; } for(i=n-2;i>=0;i--) { for(j=0;j<=n-1;j++) if(f[j]>f[j+1]) f[j]=f[j]+a[i][j]; else f[j]=f[j+1]+a[i][j]; } printf(“%dn”,f[0]);} system(“pause”);} 2：Pku acm 1953 World Cup Noise //说白了就是斐波那切数列 #include “iostream” using namespace std;int main(){ int n,m; int i; int f[100]; f[0]=2; f[1]=3; scanf(“%d”,&n); for(i=2;i<100;i++) { f[i]=f[i-1]+f[i-2]; } for(i=0;i { scanf(“%d”,&m); { printf(“Scenario #%d:n%dnn”,i+1,f[m-1]); } } } 3：Pku acm 1458 Common Subsequence Lcs经典 #include “iostream” #include “cstring” using namespace std;int setmax(int a,int b){ if(a>b) return a; else return b;} int f[8100][8100];main(){ char s1[800]; char s2[800]; int i,j; int sl1,sl2; while(scanf(“%s %s”,&s1,&s2)!=EOF) { sl1=strlen(s1); sl2=strlen(s2); for(i=0;i { f[0][i]=0; f[i][0]=0; } for(i=1;i for(j=1;j { if(s1[i-1]==s2[j-1]) f[i][j]=f[i-1][j-1]+1; else f[i][j]=setmax(f[i-1][j],f[i][j-1]); } printf(“%dn”,f[i-1][j-1]); } } 4：Pku acm 2250 Compromise记录路径的lcs #include “iostream” #include “string” using namespace std;#define N 100 struct node { string s;}s1[N],s2[N];int f[N][N];int path[N][N];string temp;int flag;void lcs(int i,int j){ if(i==0||j==0)return; if(path[i][j]==1){ lcs(i-1,j-1); { if(flag!=1){ cout< flag=1;} else cout< } else if(path[i][j]==2)lcs(i-1,j); else lcs(i,j-1);} int main(){ int i=0,j; int len1,len2; while(cin>>s1[0].s) { memset(f,0,sizeof(f)); i=1; while(1){ cin>>temp; if(temp==“#”)break; s1[i++].s=temp; } len1=i; i=0; while(1){ cin>>temp; if(temp==“#”)break; s2[i++].s=temp; } len2=i; memset(path,0,sizeof(path)); for(i=0;i<=len1;i++) for(j=0;j<=len2;j++) if(i==j)f[i][j]=1; for(i=1;i<=len1;i++) for(j=1;j<=len2;j++) { if(s1[i-1].s==s2[j-1].s) { f[i][j]=f[i-1][j-1]+1; path[i][j]=1; } else if(f[i-1][j]>=f[i][j-1]) { f[i][j]=f[i-1][j]; path[i][j]=2; } else { f[i][j]=f[i][j-1]; path[i][j]=3; } } flag=1; lcs(len1,len2); cout< } } 5：Pku acm 1159 Palindrome 回文串 带有些许优化的lcs #include “iostream” #include “string” #include “algorithm” using namespace std;int a[5005],b[5005];int c[3],d[3];string s1,s2;int main(){ int m,n=0; int i,j; while(cin>>n) { if(n==0)break; cin>>s1; } } s2=s1;reverse(s2.begin(),s2.end()); memset(a,0,sizeof(a)); memset(b,0,sizeof(b));for(i=0;i { b[0]=0; for(j=0;j { if(s1[i]==s2[j]) { b[j+1]=a[j]+1; } else if(b[j]>a[j+1]) { b[j+1]=b[j]; } else if(b[j] { b[j+1]=a[j+1]; } } for(j=0;j<=n;j++) a[j]=b[j]; } printf(“%dn”,n-b[n]);14 6：Pku acm 1080 Humman Gene Function #include “iostream” using namespace std;int f[250][250];int g[250][250];char s1[180];char s2[180];int maxnum(int x,int y,int z){ int zz= x>y?x:y; return zz>z?zz:z;} void make(){ f[1][1]=5;f[1][2]=-1;f[1][3]=-2;f[1][4]=-1;f[1][5]=-3; f[2][1]=-1;f[2][2]=5;f[2][3]=-3;f[2][4]=-2;f[2][5]=-4; f[3][1]=-2;f[3][2]=-3;f[3][3]=5;f[3][4]=-2;f[3][5]=-2; f[4][1]=-1;f[4][2]=-2;f[4][3]=-2;f[4][4]=5;f[4][5]=-1; f[5][1]=-3;f[5][2]=-4;f[5][3]=-2;f[5][4]=-1;f[5][5]=-99999;} int sw(char ch){ if(ch=='A') return 1; else if(ch=='C') return 2; else if(ch=='G') return 3; else if(ch=='T') return 4; else if(ch=='-') return 5;} int find(char ch1,char ch2){ return f[sw(ch1)][sw(ch2)];} int main(){ make(); int sl1,sl2,i,j,m; memset(g,0,sizeof(0)); cin>>m; while(m--) { cin>>sl1; cin>>s1; cin>>sl2; cin>>s2; for(i=1;i<=sl2;i++) g[0][i] = g[0][i-1]+find('-',s2[i-1]); for(i=1;i<=sl1;i++) g[i][0] = g[i-1][0]+find(s1[i-1],'-'); for(i=1;i<=sl1;i++) for(j=1;j<=sl2;j++) { g[i][j]=maxnum(g[i][j-1]+find('-',s2[j-1]),g[i-1][j]+find(s1[i-1],'-'),g[i-1][j-1]+find(s1[i-1],s2[j-1])); } cout< 7：Pku acm 2192 Zipper 判断2个字符串能否组成1个字符串 //用动态规划解决，ok[i][j]表示str1长度为i的前缀和str2长度为j的后缀能否组成目标中str中长度为i+j的前缀串 #include “iostream” using namespace std;int i,j,n;int sl1,sl2,sl3;char s1[500],s2[500],s3[500];int f[500][500];int main(){ int count=0; scanf(“%d”,&n); while(n--) {count++; memset(f,0,sizeof(f)); scanf(“%s %s %s”,s1,s2,s3); sl1=strlen(s1); sl2=strlen(s2); sl3=strlen(s3); for(j=0;j { if(s1[j]==s3[j]) f[j+1][0]=1; else break; } for(i=0;i { if(s2[i]==s3[i]) f[0][i+1]=1; else break; } for(i=0;i<=sl1;i++) for(j=0;j<=sl2;j++) { if(!(i==0&&j==0)) if(s1[i]==s3[i+j]&&f[i][j]==1) f[i+1][j]=1; if(s2[j]==s3[i+j]&&f[i][j]==1) f[i][j+1]=1; } printf(“Data set %d: ”,count); if(f[sl1][sl2]==1) printf(“yesn”); else printf(“non”); } } 8：Pku acm 3356 AGTC 一个字符串到另一个的最小步骤 #include “iostream” #include “string” using namespace std;int setmin(int x,int y,int z){ int xx=x>y?y:x; return xx>z?z:xx;} string s1,s2;int f[1005][1005];int main(){ int n,m; int i,j; while(cin>>n) { cin>>s1; cin>>m; cin>>s2; for(i=0;i<=n;i++) f[i][0]=i; for(i=0;i<=m;i++) f[0][i]=i; for(i=1;i<=n;i++) for(j=1;j<=m;j++) { if(s1[i-1]==s2[j-1]) f[i][j]=setmin(f[i-1][j]+1,f[i][j-1]+1,f[i-1][j-1]); else f[i][j]=setmin(f[i-1][j]+1,f[i][j-1]+1,f[i-1][j-1]+1); } cout< } } 9：Pku acm 1887 Testing the CATCHER最长下降子序列 #include “iostream” using namespace std;int a[32769],f[32769];int main(){ int i,j,n,max; int count=0; while(1) { count++; scanf(“%d”,&a[0]); if(a[0]==-1)break; i=1; while(1) { scanf(“%d”,&a[i]); if(a[i]==-1) break; i++; } n=i; max=0; memset(f,0,sizeof(f)); for(i=1;i<=n;i++) { f[i]=1; for(j=0;j<=i;j++) { if(a[j-1]>a[i-1]&&f[j]+1>f[i]) f[i]=f[j]+1; if(f[i]>max) max=f[i]; } } printf(“Test #%d:n”,count); printf(“ maximum possible interceptions: %dnn”,max); } } 10：Pku acm 2533 Longest Ordered Subsequence最长上升子序列 #include “iostream” using namespace std;int f[10000];int a[10000];int main(){ int n,i,j,max; while(scanf(“%d”,&n)!=EOF) { for(i=0;i { scanf(“%d”,&a[i]); } memset(f,0,sizeof(f)); max=0; for(i=1;i<=n;i++) { f[i]=1; for(j=0;j<=i;j++) if(a[j-1] f[i]=f[j]+1; if(f[i]>max) max=f[i]; } printf(“%dn”,max); } } 11：Pku acm 1631 Bridging signals最长上升子序列的加强版….二分法 #include “iostream” #include “string” using namespace std;#define N 50000 int f[N];int a[N];int main(){ int n,m,i,j,max; scanf(“%d”,&n); while(n--) { max=-99; memset(f,0,sizeof(f)); scanf(“%d”,&m); for(i=0;i { scanf(“%d”,&a[i]); // f[i]=a[i]; } f[1]=a[0]; int s=1; int l,r,mid; for(i=1;i { if(f[s] f[++s]=a[i]; else { l=0; r=s; mid=(l+r)>>1; while(l<=r) { mid=(l+r)>>1; f[mid] } f[l]=a[i]; } } printf(“%dn”,s);} } 12：Pku acm 1157 LITTLE SHOP OF FLOWERS 该题也是经典的动态规划，题目叙述的依然很麻烦，其实简化一下就是这样的：例如下面这个例子就是：3表示行，5表示列，然后在下面的3行5列每一行选一个数，使这3个数最大，要求选的数列数必须依次增大，就是从左上方想右下方选3个数使和最大。3 5 7 23-5-24 16 5 21-4 10 23-21 5-4-20 20 #include “iostream” using namespace std;#define N 5000 int f[N][N];int w[N][N];int main(){ int n,m,i,j,k;while(cin>>n>>m){ for(i=0;i for(j=0;j cin>>w[i][j]; for(i=0;i for(j=0;j f[i][j]=-50000; for(i=1;i f[1][i]=w[0][i-1]; for(i=2;i<=n;i++) { for(j=1;j<=m;j++) { if(j>=i) for(k=1;k if(f[i][j] f[i][j]=f[i-1][k]+w[i-1][j-1]; } } int max=-50000; for(i=0;i<=m;i++) if(f[n][i]>max) max=f[n][i]; printf(“%dn”,max);} } 13：Pku acm 1088 滑雪 1 2 3 4 5 16 17 18 19 6 15 24 25 20 7 14 23 22 21 8 13 12 11 10 9 一个人可以从某个点滑向上下左右相邻四个点之一，当且仅当高度减小。在上面的例子中，一条可滑行的滑坡为24-17-16-1。当然25-24-23-...-3-2-1更长。事实上，这是最长的一条。输出最长区域的长度。 #include “iostream” using namespace std;int h[100][100];int f[100][100];int dir[4][2]={{-1,0},{0,1},{1,0},{0,-1}};int r,c;bool judge(int x,int y){ if(x>=0&&y>=0&&x return true; else return false;} int dp(int i,int j){ int max=0,xi,yi,k; if(f[i][j]!=0) return f[i][j]; for(k=0;k<4;k++) { xi=i+dir[k][0]; yi=j+dir[k][1]; if(judge(xi,yi)&&h[i][j]>h[xi][yi]) { int num=dp(xi,yi); if(num>max) max=num; } } f[i][j]=max+1; return max+1;} int main(){ int i,j; int temp,max; while(cin>>r>>c) { for(i=0;i for(j=0;j { cin>>h[i][j]; } memset(f,0,sizeof(f)); max=0; for(i=0;i { for(j=0;j { temp=dp(i,j); max=max>temp?max:temp; } } cout< } } 14：hdoj1003 max num #include “iostream” using namespace std;int f[100005];int a[100005];int main(){ int num,n,i,j; int st,end,now,max; int flag; int count=0; int k;cin>>num; while(num--) { count++; cin>>n; for(i=0;i cin>>a[i]; now=0; max=-999; k=1; for(i=0;i { now+=a[i]; if(now>max) { max=now; end=i+1; st=k; } if(now<0) { now=0; k=i+2; } } printf(“Case %d:n”,count); printf(“%d %d %dn”,max,st,end); if(num!=0)printf(“n”); } return 0; } 15：Pku 1050 To the Max最大线段和的加强板…..二维的 #include “iostream” using namespace std;int n,i,j,cnt,now,maxx,k;int a[150][150];int s[150][150][150];int main(){ while(scanf(“%d”,&n)!=EOF) { for(i=1;i<=n;i++) for(j=1;j<=n;j++) { scanf(“%d”,&a[i][j]); s[i][i][j]=a[i][j]; } for(i=1;i for(j=i+1;j<=n;j++) for(k=1;k<=n;k++) { s[i][j][k]=s[i][j-1][k]+a[j][k]; } maxx=0; for(i=1;i<=n;i++) for(j=1;j<=n;j++) { cnt=0; now=0; for(k=1;k<=n;k++) { cnt+=s[i][j][k]; if(cnt>now) now=cnt; if(cnt<0) cnt=0; } if(now>maxx)maxx=now; } printf(“%dn”,maxx); } return 0;} 16：Pku 1014 dividing 实在不会做先抄个代码 #include bool opt[60000]; int num=0; int mid,max; int stone[7]; int input() { scanf(“%d%d%d%d%d%d”,&stone[1],&stone[2],&stone[3],&stone[4],&stone[5],&stone[6]); if(!stone[6]&&!stone[1]&&!stone[2]&&!stone[3]&&!stone[4]&&!stone[5]){return 1;} //读到末行 num++; printf(“Collection #%d:n”,num); mid=0; for(int i=1;i<=6;i++)mid+=stone[i]*i; if(mid % 2 ==1)//明显的剪枝 { printf(“Can't be divided.nn”); return 2; } else mid/=2;//我们的任务就是求opt return 0; } void dp() { memset(opt,0,60000);//初始化，opt所有成员为false opt[0]=true;//opt[0]显然是true max=0;//当前最大值是0 for(int i=1;i<=6;i++) { if(stone[i]>0) { for(int j=max;j>=0;j--) // 从当前最大值开始往下算 if(opt[j])//找到可行的j { if(opt[mid]) //判断是否已经求出结果 { printf(“Can be divided.nn”); return; } for(int k=1;k<=stone[i];k++)//在刚找到的可行j基础上加石头.{ if(j+k*i>mid || opt[j+k*i])break;//如果已经大于总价值的一半mid，或opt[j+k*i]已计算，跳出循环 opt[j+k*i]=true; } } } max=max+i*stone[i];//更新当前最大值 if(max>mid)max=mid; //如果当前最大值超过了mid，对其赋值为mid } printf(“Can't be divided.nn”);//如果从1到6循环完一遍后仍然没有算出opt[mid]，说明无解 } int main() { while(1) { int t=input(); switch(t) { case 1 : return 0; //读到末行，结束 case 2 : continue;//读到明显的剪枝 default : dp(); } } return 0; } 17: Pku acm 1160 post office 贴代码 题目给出m个村庄及其距离，给出n个邮局，要求怎么建n个邮局使代价最小。思路：用opt[i][j]记录把前i个邮局建到前j个村庄中的最优解，用cost[i][j]记录所有在i到j村庄中，建1个邮局的最小代价。显然邮局应该设到中点。让前i个邮局覆盖前j个村庄，第i+1个邮局覆盖第j+1至j+k个村庄(j+k<=n)，则状态转移方程为 w[i+1][j+k]=min{w[i][j]+cost[j+1][j+k];}(k+j<=n)Cost数组存放从i到j中有一个邮局的最小代价，显然该邮局应该放在中间 W[i][j] 表示前i个邮局覆盖前j个村庄的最小代价，对于i=1来说，w[i][j] = cost[i][j],让前2个邮局覆盖前j个村庄，也就是i=2的情况，可能是一下情况的最优解：第一个邮局覆盖第一个村庄，第二个村庄覆盖2-j个村庄，或者第一个邮局覆盖第1-2个村庄，第二个村庄覆盖3-j个村庄，第一个邮局覆盖第1-3个村庄，第二个村庄覆盖4-j个村庄，等等等等 #include “iostream” using namespace std;int cost[310][310];int w[310][310];#define max 3000000 int main(){ int i,j,k,m,n,mid,q,v[310];while(scanf(“%d%d”,&m,&n)!=EOF){ for(i=1;i<=m;i++) scanf(“%d”,&v[i]); memset(cost,0,sizeof(cost)); for(i=1;i<=m;i++) for(j=i;j<=m;j++) { mid=(i+j)/2; for(k=i;k<=mid;k++) cost[i][j]=cost[i][j]+v[mid]-v[k]; for(k=mid+1;k<=j;k++) cost[i][j]=cost[i][j]+v[k]-v[mid]; } for(i=0;i<=n;i++) for(j=0;j<=m;j++) w[i][j]=max; w[0][0]=0; for(i=0;i<=n;i++) for(j=0;j<=m;j++) if(w[i][j] { for(k=1;k<=m-j;k++) { q=w[i][j]+cost[j+1][j+k]; if(w[i+1][j+k]>q) w[i+1][j+k]=q; } } printf(“%dn”, w[n][m]);} return 0;} 18: pku acm 1015 Jury Compromise 题目大意：在遥远的国家佛罗布尼亚，嫌犯是否有罪，须由陪审团决定。陪审团是由法官从公众中挑选的。先随机挑选n个人作为陪审团的候选人，然后再从这n个人中选m人组成陪审团。选m人的办法是：控方和辩方会根据对候选人的喜欢程度，给所有候选人打分，分值从0到20。为了公平起见，法官选出陪审团的原则是：选出的m个人，必须满足辩方总分和控方总分的差的绝对值最小。如果有多种选择方案的辩方总分和控方总分的之差的绝对值相同，那么选辩控双方总分之和最大的方案即可。 分析：显然本题如不用DP的话，显然会超时。我们将第i个人的辩方和控方的差记录在sub[i]中，将第i个人的辩方和控方的和记录在plus[i]中，现在用f(j,k)表示取j个侯选人中，辩控和最大的那个方案。如果没法选j个人使其控辩差为k的话，令f(j,k)=-1;本题的要求选出m个人，即最终解为f(m,k)，(-21*m<=k<=21*m)其中k的绝对值最小且有解。显然f(j,k)是某个可行方案f(j-1,x)(-21*m<=x<=21*m)演变而来。可行方案f(j-1,x)演变成f(j,k)的条件是:存在某个侯选人i，它在方案f(j-1,x)中没有被选上，且x+sub[i]=k,并且在所有满足上述条件的方案中，f(j-1,x)+plus[i]最大。此时f(j-1,x)+plus[i]=f(j,k)。在上述推导中，另一个难点是如何标记i是不是已经在方案f(j-1,x)中。此时，我们可以用一个path(j,k)来记录相应的f(j,k)中最后选的人。例如上面的,则path(j,k)=i;倒数第二个人选的编号为path(j-1,k-sub[i]),依次类推，我们就能求出某个方案中所有人的编号。实际解题中，则于控辩差有可能为负，由于控辩差的范围为[-21*m,21*m]我们可将所有控辩差加上m*21来解决，保证其值为正。#include int m,n;int f[21][850];int path[21][850];int PLUS[500],sub[500],ans[21],la,size;int main(){ int i,ii,jj,j,k,a,b,test=1; while(cin>>n>>m&&n+m) { size=21*m; for(i=1;i<=n;i++) { cin>>a>>b; PLUS[i]=a+b; sub[i]=a-b; } memset(f,-1,sizeof(f)); memset(path,-1,sizeof(path)); f[0][size]=0;path[0][size]=0; for(i=1;i<=n;i++)//先算出第1个人的编号 { if(f[1][size+sub[i]] { path[1][size+sub[i]]=i; f[1][size+sub[i]]=PLUS[i]; } } for(i=1;i { for(j=0;j<2*size;j++) { if(path[i][j]>=0) { for(k=1;k<=n;k++) { if(f[i+1][j+sub[k]] { for(jj=i,ii=j;jj>=1;jj--)//顺藤摸瓜.判断第k个人有没有出现过 { if(path[jj][ii]==k)break; ii-=sub[path[jj][ii]]; } if(jj<1) { path[i+1][j+sub[k]]=k; f[i+1][j+sub[k]]=f[i][j]+PLUS[k]; } } } } } } for(j=0;j<=2*size;j++)//取绝对值最小的作为最优解 { if(f[m][size+j]>=0||f[m][size-j]>=0) { if(f[m][size+j]>f[m][size-j]) i=size+j; else i=size-j; break; } } cout<<“Jury #”< cout<<“Best jury has value ”<<(f[m][i]+i-size)/2<<“ for ”<<(f[m][i]-i+size)/2<<“ for defence:”< la=0; for(j=m,k=i;j>=1;j--) { ans[la++]=path[j][k]; k-=sub[ans[la-1]]; } sort(ans,ans+la);//排序输出 for(i=0;i cout<<“ ”< cout< } return 0; prosecution and value } 19: hdoj 2546饭卡 电子科大本部食堂的饭卡有一种很诡异的设计，即在购买之前判断余额。如果购买一个商品之前，卡上的剩余金额大于或等于5元，就一定可以购买成功（即使购买后卡上余额为负），否则无法购买（即使金额足够）。所以大家都希望尽量使卡上的余额最少。 某天，食堂中有n种菜出售，每种菜可购买一次。已知每种菜的价格以及卡上的余额，问最少可使卡上的余额为多少。Input 多组数据。对于每组数据： 第一行为正整数n，表示菜的数量。n<=1000。 第二行包括n个正整数，表示每种菜的价格。价格不超过50。第三行包括一个正整数m，表示卡上的余额。m<=1000。n=0表示数据结束。 Output 对于每组输入,输出一行,包含一个整数，表示卡上可能的最小余额。Sample Input 1 50 5 10 1 2 3 2 1 1 2 3 2 1 50 0 Sample Output-45 32 #include #include using namespace std; int a[1002]; int b[1002]; void dfs(int x); int m; int sum,num,ans,flag; int main() { int i,j,k,n,t; while(scanf(“%d”,&n)!=EOF && n) { memset(b,0,sizeof(b)); sum = 0; for(i=0;i { scanf(“%d”,&a[i]); sum += a[i]; } scanf(“%d”,&m); if(sum+5 <= m)//如果余额很大的情况 { printf(“%dn”,m-sum); continue; } if(m < 5)//如果本来的余额小于5那么就不用计算了 { printf(“%dn”,m); continue; } sort(a,a+n); //开始遍历: //找到临界大于m-5的最小的和 ans = 0; num = m-5; for(i=n-2;i>=0;i--) { int maxnum = 0; for(j=i+1;j<=n-2;j++) { if((b[j] > maxnum)&&(a[i]+b[j]<=num)) maxnum = b[j]; } if(a[i]+maxnum == num) { ans = num; break; } else if(a[i]+maxnum < num) { b[i] = a[i]+maxnum; } if(b[i] > ans) ans = b[i]; } printf(“%dn”,m-ans-a[n-1]); } return 0; } 20:pku 1837 Balance 输入一个天平若干（<=20）挂钩的位置，将若干（<=20）砝码挂到天平上，问有多少种使天平挂平衡的方法。 解题思路： 用一个二维数组a[x][y+mid]记录挂x个砝码时到y这个值的方法数，将砝码一一挂上，最后记录所有砝码都挂上时的t[x][MID]的值，详见代码。状态方程:a[i][j+value[i]*hook[k]]+=a[i-1][j];背包问题 #include “stdio.h” #include “stdlib.h” #define MID 7500 int a[21][2*MID];int val[21];int hook[21];int main(){ int m,n; int i,j,k; while(scanf(“%d%d”,&m,&n)!=EOF) { memset(a,0,sizeof(a)); for(i = 1;i<=m;i++) scanf(“%d”,&hook[i]); for(i = 1;i<=n;i++) scanf(“%d”,&val[i]); for(j = 1;j<=m;j++) a[1][val[1]*hook[j]+MID]++; for(i =2;i<=n;i++) for(j = 0;j<=2*MID;j++) for(k = 1;k<=m;k++) if(a[i-1][j]!=0) { a[i][j+val[i]*hook[k]]+=a[i-1][j]; } printf(“%dn”,a[n][MID]); } return 0;} 21: pku 3267 The Cow Lexicon 题目意思就是给出一个字符序列，同时给出已知的字符序列（单词），问至少需要去掉多少个字符之后能够将给出的字符序列变成已知的字符序列（单词）的组合（根据题目意思，没有字符是已知字符序列组合的一种情况）。 可以用s[i]表示从第一个字符到第i个字符中，满足题目要求去掉的最少字符数。那么s[i]=min（num[k，i]+s[k-1]），其中num[k，i]表示从第k个字符到第i个字符匹配到某一个单词时所需要的去掉的最少字符数。当然匹配时是需要穷举所有的单词的。匹配的时候如果从前往后比较的话，需要加入剪枝（如果k+len[j]〉i的话肯定就是不行的），这样的话就可以采取从后往前的比较方式，这样之前需要将每个单词的长度保存到len[j]当中。 #include scanf(“%s”,str+1); for(i=1;i<=m;i++){ scanf(“%s”,word[i]+1); len[i]=strlen(word[i]+1); } s[0]=0; for(i=1;i<=l;i++){ min=i; for(j=1;j<=m;j++){ pos_str=i; pos_word=len[j]; num=0; while(pos_str>=1&&pos_word>=1){ if(str[pos_str]==word[j][pos_word]){ pos_str--; pos_word--; } else { pos_str--; num++; } } if(pos_word<=0 && min>num+s[pos_str]){ min=num+s[pos_str]; } } s[i]=min; } printf(“%dn”,s[l]); } system(“PAUSE”); return 0;} 22:Pku 1742 Coins 编写一个程序，读入n，m。有币值A1、A2、A3…、An的硬币，对应各有C1、C2、C3、…、Cn数量的硬币，问它们能够在1~m元中组合成多少中不同的币值？ #include memset(dp,0,sizeof(dp));for(int i=1;i<=n;i++)scanf(“%d”,&a[i]);for(int i=1;i<=n;i++) scanf(“%d”,&c[i]);for(int i=0;i<2;i++)dp[i][0]=1;memset(flag,0,sizeof(flag));memset(flagans,0,sizeof(flagans));int from=0,to=1;for(int i=1;i<=n;i++){ memset(flag,0,sizeof(flag)); for(int j=1;j<=m;j++) { dp[to][j]=dp[from][j]; if(dp[to][j]==0&&j>=a[i]&&dp[to][j-a[i]]&&flag[j-a[i]]+1<=c[i]) { dp[to][j]=1; flagans[j]=1; flag[j]=flag[j-a[i]]+1; } } int temp; temp=from; from=to; to=temp;} int ans=0;for(int i=1;i<=m;i++){ // cout< ans+=flagans[i];} printf(“%dn”,ans);} system(“pause”);return 0;} 吉林师范大学计算机学院 教 案 课 程 名 称 院系 级 C 程序设计(算法部分) 计算机学院计算机科学与技术09级 教研室(系、实验室)计算机基础教研室5101 授 课 班 级 09计算机科学与技术3班 实习 生 郑言 系指导教师 滕国文 吉林师范大学计算机学院 二○一二年四月二十五日（星期三5，6节） 课型章节： 动态规划基本思想 基要本参教考材资和料主： 算法设计与分析》 教学目的： 本课程以C语言为教授程序设计的描述语言，结合语言介绍程序设计的基本原理、技巧和方法。主要讲授内容包括程序设计动态规划基本概念，动态规划的基本步骤，动态规划问题的特征。通过本课程的学习，为算法更好的学习，以及能用计算机解决一些实际问题打下坚实的基础。教学基本要求： 掌握C语言中动态规划的基本概念，动态规划的基本步骤，动态规划问题的特征。并能熟练使用C语言动态规划思想解决一些简单程序问题；掌握一些基本算法结构及相关方法；熟悉程序设计的思想和编程技巧。重点： 动态规划基本概念，动态规划的基本步骤，动态规划问题的特征。难点: 动态规划的基本步骤 课型： 理论课 教法： 1.多媒体讲解 2.举例讲解 教学内容及过程： 1.课前回顾： 枚举法: 在进行归纳推理时，如果逐个考察了某类事件的所有可能情况，因而得出一般结论，那么这结论是可靠的，这种归纳方法叫做枚举法． 2.数塔问题 有形如下图所示的数塔，从顶部出发，在每一结点可以选择向左走或是向右走，一直走到底层，要求找出一条路径，使路径上的值最大。简单的进行选举方法的引导，让同学们主动思考到动态规划的思想上了。考虑一下： 从顶点出发时到底向左走还是向右走应取决于是从左走能取到最大值还是从右走能取到最大值，只要左右两道路径上的最大值求出来了才能作出决策。 同样，下一层的走向又要取决于再下一层上的最大值是否已经求出才能决策。这样一层一层推下去，直到倒数第二层时就非常明了。 如数字2，只要选择它下面较大值的结点19前进就可以了。所以实际求解时，可从底层开始，层层递进，最后得到最大值。 结论：自顶向下的分析，自底向上的计算。#include return x;else return y;} main(){ int a[100][100];int i,j,n;scanf(“%d”,&n);for(i=0;i for(j=0;j<=i;j++) scanf(“%d”,&a[i][j]);for(i=n-2;i>=0;i--) for(j=0;j<=i;j++) { a[i][j]+=max(a[i+1][j],a[i+1][j+1]); } printf(“%dn”,a[0][0]);} 3.总结“动态规划的基本思想” 如果各个子问题不是独立的，不同的子问题的个数只是多项式量级，如果我们能够保存已经解决的子问题的答案，而在需要的时候再找出已求得的答案，这样就可以避免大量的重复计算。由此而来的基本思路是，用一个表记录所有已解决的子问题的答案，不管该问题以后是否被用到，只要它被计算过，就将其结果填入表中。 4.总结“动态规划的基本步骤” 动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值（最大值或最小值）的那个解。设计一个动态规划算法，通常可以按以下几个步骤进行： （1）找出最优解的性质，并刻画其结构特征。（2）递归地定义最优值。 （3）以自底向上的方式计算出最优值。 （4）根据计算最优值时得到的信息，构造一个最优解。 其中（1）——（3）步是动态规划算法的基本步骤。在只需要求出最优值的情形，步骤（4）可以省去。若需要求出问题的一个最优解，则必须执行步骤（4）。此时，在步骤（3）中计算最优值时，通常需记录更多的信息，以便在步骤（4）中，根据所记录的信息，快速构造出一个最优解。 5.总结“动态规划问题的特征” 动态规划算法的有效性依赖于问题本身所具有的两个重要性质： 1、最优子结构：当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质。 2、重叠子问题：在用递归算法自顶向下解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只解一次，而后将其解保存在一个表格中，在以后尽可能多地利用这些子问题的解。6.思考： 《免费馅饼》 题目描述: 都说天上不会掉馅饼，但有一天gameboy正走在回家的小径上，忽然天上掉下大把大把的馅饼。说来gameboy的人品实在是太好了，这馅饼别处都不掉，就掉落在他身旁的10米范围内。馅饼如果掉在了地上当然就不能吃了，所以gameboy马上卸下身上的背包去接。但由于小径两侧都不能站人，所以他只能在小径上接。由于gameboy平时老呆在房间里玩游戏，虽然在游戏中是个身手敏捷的高手，但在现实中运动神经特别迟钝，每秒种只有在移动不超过一米的范围内接住坠落的馅饼。现在给这条小径如图标上坐标： 为了使问题简化，假设在接下来的一段时间里，馅饼都掉落在0-10这11个位置。开始时gameboy站在5这个位置，因此在第一秒，他只能接到4,5,6这三个位置中期中一个位置上的馅饼。问gameboy最多可能接到多少个馅饼？（假设他的背包可以容纳无穷多个馅饼） #include 7.课后作业 杭电ACM 1003、1466、1087、1159、1176、1058、1069、2059、2084 课文题目中的标点 我们学习的课文中，好些题目上有标点符号，它们大致可分为以下几种： 一、引用文中的一句话 如《“你们想错了”》、《“兄弟便是朱德”》、《“我是你的儿子”》这三篇课文的题目是直接引用文中的一句话，因此加上了引号。 二、表示语句的停顿 课文题目中如有停顿，必须用逗号隔开，如《再见了，亲人》、《别了，我爱的中国》、《火警，119》、《祖国，我终于回来了》、《延安，我把你追寻》等。 三、表示某种特殊语意 题目中有某种特殊语意时，也常用引号，如《“私塾先生”》、《我的“自白”书》等。其中的“私塾先生”指的是陈毅同志。 作业 1 1 动态规划练习： 为保证某一设备的正常运转，需备有三种不同的零件 E 1 , E 2, E 3 。若增加备用零件的数量，可提高设备正常运转的可靠性，但增加了费用，而投资额仅为8000 元。已知备用零件数与它的可靠性和费用的关系如表1 所示。 现要求在既不超出投资额的限制，又能尽量提高设备运转的可靠性的条件下，问各种零件的备件数量应是多少为好？要写出计算程序。 解： 设投资顺序为 E1，E2，E3，阶段编号逆向编号，即第一阶段计算给E3 投资的效果。设ks 为第 k 阶段的剩余款，kx 为第 k 阶段的拨款额，状态转移方程为k k kx s s 1，目标函数为)1()1()1(max3 2 1P P P f ,其中1P，2P，3P 分别为 E1，E2，E3 增加的可靠性 第一阶段：对 E3 的投资效果 决策表： s1x1 0 2 3 4 *1x f1 0 1 0 1 1 1 0 1 2 1 1.1 1.1 3 1 1.1 1.21.2 4 1 1.1 1.2 1.7 4 1.7 1 1.1 1.2 1.7 4 1.7 6 1 1.1 1.2 1.7 4 1.7 7 1 1.1 1.2 1.7 4 1.7 8 1 1.1 1.2 1.7 4 1.7 第二阶段，对 E2 的投资效果 由于 E1 最多只需 3000，故 52 s 千 决策表： s2x2 0 3 5 6 *2x f2 5 1.7 1.32 1.51.5 6 1.7 1.44 1.5 1.9 6 1.9 7 1.7 2.04 1.65 1.9 3 2.04 8 1.7 2.04 1.8 2.09 6 2.09 第三阶段：对 E1 的投资效果 决策表: s3x3 0 2 3 4 *3x R3 8 2.09 2.09 1.8 0.7 0,2 2.09 回溯：有两组最优解(1)x3=0,x2=3,x1=2,maxf=2.09(2)x3=1,x2=3,x1=0,maxf=2.092 层次分析法练习：你已经去过几家主要的摩托车商店，基本确定将从三种车型 中选购一种，你选择的标准主要有：价格、耗油量大小、舒适程度和外观美观情况。经反复思考比较，构造了它们之间的成对比较判断矩阵。 三种车型（记为 a , b , c）关于价格、耗油量、舒适程度和外表美观情况的成对比较判断矩阵为： （1）根据上述矩阵可以看出四项标准在你心目中的比重是不同的，请按由重到轻顺序将它们排出。 （2）哪辆车最便宜、哪辆车最省油、哪辆车最舒适、哪辆车最漂亮？（3）用层次分析法确定你对这三种车型的喜欢程度（用百分比表示）。 解： (1)由重到轻依次是价格、耗油量、舒适程度和外表美观情况(2)C 车最便宜，A 车最省油，A 车最舒适，B 车最漂亮(3)a、建立层次模型： 目标层：选择哪种车 准则层：价格 耗油情况 舒适度 外表美观度 方案层：A 车型 B 车型 C 车型 b、成对比较阵题目当中已给出 c、计算权向量并做一致性检验 运行结果得到权向量为 w=(0.5820,0.2786,0.0899,0.0495),CR=0.0734<0.1,通过一致性检验 d、计算组合权向量。 由运行结果得知方案层对目标层的权重向量为（0.4091，0.4416，0.1493） 则可得出结论应该选购 B 车型 附（代码）： clc a=[1,3,7,8 1/3,1,5,5 1/7,1/5,1,3 1/8,1/5,1/3,1];%一致矩阵 [x,y]=eig(a);eigenvalue=diag(y);lamda=max(eigenvalue);ci1=(lamda-4)/3;cr1=ci1/0.9 w1=x(:,1)/sum(x(:,1))b1=[1,2,3;1/2,1,2;1/3,1/2,1];[x,y]=eig(b1);eigenvalue=diag(y);lamda=eigenvalue(1);ci21=(lamda-3)/2;cr21=ci21/0.58 w21=x(:,1)/sum(x(:,1))b2=[1 1/5 1/2;5 7;2 1/7 1];[x,y]=eig(b2);eigenvalue=diag(y);lamda=eigenvalue(1);ci22=(lamda-3)/2;cr22=ci22/0.58 w22=x(:,1)/sum(x(:,1))b3=[1 5;1/3 4;1/5 1/4 1];[x,y]=eig(b3);eigenvalue=diag(y);lamda=eigenvalue(1);ci23=(lamda-3)/2;cr23=ci23/0.58 w23=x(:,1)/sum(x(:,1))b4=[1 1/5 3;5 7;1/3 1/7 1];[x,y]=eig(b4);eigenvalue=diag(y);lamda=eigenvalue(1);ci24=(lamda-3)/2;cr24=ci24/0.58 w24=x(:,1)/sum(x(:,1))w_sum=[w21,w22,w23,w24]*w1 ci=[ci21,ci22,ci23,ci24];cr=ci*w1/sum(0.58*w1) 正确使用标题中的标点？ 学生在写文章时，仅做到在文内正确使用标点符号是远远不够的。我在教学中发现，一些学生在文章标题中有滥用标点的现象。因此，教师应在文章标题中如何使用标点上对学生做正确引导。 一、文章题目是单句时，句末不用句号 例：在山的那边 二、文章题目是复句时，中间可用逗号，句末不用句号 例：十年，还一副尊严 三、题目表疑问语气的用问号，表感叹语气的用叹号 例：还有人活着吗？ 短些，再短些！ 四、题目中有停顿语气的，可用以下方法处理 (1)用逗号、顿号或间隔号 例：啊，金色的秋天 党在农村的方针、政策、法规 夏夜·秋色 (2)“空格”表示停顿 例：关注学校关注家庭 (3)分行排列表语气停顿 例：锻炼心理品质 培育健康心理 五、根据标题内容，也可用其它符号(如引号、破折号、省略号、书名号等等) 例：“诺曼底”号遇难记 下辈子，我们还当母子 一位痛失儿子的母亲自述 风乍起…… 徐霞客和《徐霞客游记》 承德县第二中学 李桂琴 五道河中心校包军第二篇：动态规划教案
第三篇：课文题目中的标点
第四篇：动态规划作业
第五篇：文章题目中的标点符号
点击咨询 