http://47.99.179.148/problemlist.php
1001 注意两个问题，使用string 和getline 函数
#include<iostream> #include<cstring> using namespace std; int main() { int n; cin>>n; string a[n+1]; int sum[n+1]; memset(sum,0,sizeof(sum)); getchar();///warning must be use the getchar() function to clear the enter keyboard and then use the getline() function for(int i=0;i<n;i++) { // cin>>a[i]; the cin cant get space from the keybroad must use the getline() function getline(cin,a[i]); for(int j=0;j<a[i].length();j++) { int t=a[i][j]-'0'; if(t<=9 && t>=0) { sum[i]++; } } } for(int i=0;i<n;i++) { cout<<sum[i]<<endl; } return 0; }1009 //最长递减序列问题LDS
#include<iostream> #include<algorithm> using namespace std; int main() { int m; cin>>m; int n; int num[100]; //record the number of height int result[100];//output int dp[100]; int t=0; for(int ii=0;ii<m;ii++) { cin>>n; for(int jj=0;jj<n;jj++ ) { cin>>num[jj]; } /* 错解 不是从第一个开始，只要选择最长的序列即可 // int log[100]; // int flag=num[0]; // memset(log,0,sizeof(log)); // // log[0]=1;//第一位默认为基准，序列长度为1 // //所以记录当前位值从第一位开始的最长序列，当前的值与之前的所有值相比较 // //d当前的值小于前面某一位长度的值时，在其长度上加一，所以一定能得到最长的那个值 // //需要注意，当当前某值比num[0]大时，则没必要比较 // // for(int k=1;k<n;k++) // { // if(num[k]>=flag) //因为是以第一位为基准，所以当大于第一位的数据，则直接除去，不用比较，否则后面的数据会受影响 // { // log[k]=-1; // continue; // } // for(int L=0;L<k;L++) // { // if(log[L] == -1) // { // continue; // } // // if(num[k]<num[L]) // { // log[k]=log[L]+1; //单纯的在前面的数据的标记上加一，无法区分最长的 ex：8 9 7 6 7 5 6 4,当在5的时候，无法单纯的在前面的7的标记为2上加一，明显8 7 6 5更长， // // 但是可以考虑选择最长的序列加一，这就是LDS中的第二个判断条件的缘由 // } // } // // } */ //直接使用LDS，longest descreasing sequence,寻找最长子序列 //考虑到1008题，要求输出所有的最长子序列，直接寻找所有的最长子序列 //输出所有的个数，则为1008题题解 int ans=-1; for(int i=0;i<n;i++) { dp[i]=1; for(int j=0;j<i;j++) { if(num[i]<num[j] && (dp[j]+1 > dp[i])) { dp[i]=dp[j]+1; } } ans=max(ans,dp[i]); } result[t++]=ans; } for(int i=0;i<m;i++) { cout<<result[i]<<endl; } }1014
//最大子序列和问题，利用DP #include<iostream> #include<algorithm> #include<cstring> using namespace std; int num[50000];//将大数组定义为全局变量，放置在静态存储中可以防止溢出，同时可以自动赋值为0 int dp[50000]; int result[10000]; bool cmp(int a,int b) { return a>b; } int main() { int m; cin>>m; int n; int k=0; for(int ii=0;ii<m;ii++) { cin>>n; for(int jj=0;jj<n;jj++) { cin>>num[jj]; } dp[0]=num[0]; for(int i=1;i<n;i++) { dp[i]=max(dp[i-1]+num[i],num[i]);//dp存储的是以当前位置结尾的最大值，两种选择 1：其本身最大 2 ：其本身加上前一数据最大值， 比较这两者即可得出当前位置下的最大 } //从0开始，一层层的递推过去 sort(dp,dp+n,cmp); result[k++]=dp[0]; memset(dp,0,sizeof(dp)); memset(num,0,sizeof(num)); } for(int i=0;i<m;i++) { cout<<result[i]<<endl; } return 0; }