Description
One day Teddy met a old man in his dream , in that dream the man whose name was“RuLai” gave Teddy a problem :?
Given an N , can you calculate how many ways to write N as i * j + i + j (0 < i <= j) ??
Teddy found the answer when N was less than 10…but if N get bigger , he found it was too difficult for him to solve.?
Well , you clever ACMers ,could you help little Teddy to solve this problem and let him have a good dream ??
Input
Output
Sample Input
Sample Output
1 #include<stdio.h> 2 #include<math.h> 3 const int MAXN=100010; 4 int main(){ 5 __int64 N,ans; 6 int T; 7 scanf("%d",&T); 8 while(T--){ 9 ans=0; 10 scanf("%I64d",&N); 11 N++; 12 int flot=0; 13 for(int i=2;i<=sqrt(N);i++)if(N%i==0)ans++; 14 printf("%I64d\n",ans); 15 } 16 return 0; 17 }
Description
怎么辦呢?多搞幾套系統唄!你說說倒蠻容易,成本呢?成本是個大問題啊.所以俺就到這里來求救了,請幫助計算一下最少需要多少套攔截系統.?
Input
Output
Sample Input
Sample Output
1 #include<stdio.h> 2 #include<stdlib.h> 3 #include<vector> 4 #include<algorithm> 5 using namespace std; 6 const int MAXN=30010; 7 vector<int>vec; 8 int main(){ 9 int N,x; 10 while(~scanf("%d",&N)){ 11 int top=0; 12 vec.clear(); 13 for(int i=0;i<N;i++){ 14 scanf("%d",&x); 15 if(lower_bound(vec.begin(),vec.end(),x)==vec.end())vec.push_back(x); 16 else *lower_bound(vec.begin(),vec.end(),x)=x; 17 } 18 printf("%d\n",vec.size()); 19 } 20 return 0; 21 }
Description
"The second problem is, given an positive integer N, we define an equation like this:?
??N=a[1]+a[2]+a[3]+...+a[m];?
??a[i]>0,1<=m<=N;?
My question is how many different equations you can find for a given N.?
For example, assume N is 4, we can find:?
??4 = 4;?
??4 = 3 + 1;?
??4 = 2 + 2;?
??4 = 2 + 1 + 1;?
??4 = 1 + 1 + 1 + 1;?
so the result is 5 when N is 4. Note that "4 = 3 + 1" and "4 = 1 + 3" is the same in this problem. Now, you do it!"?
Input
Output
Sample Input
Sample Output
1 #include<stdio.h> 2 #include<string.h> 3 int main(){ 4 int N,a[150],b[150]; 5 while(~scanf("%d",&N)){ 6 for(int i=0;i<=N;i++)a[i]=1,b[i]=0; 7 for(int i=2;i<=N;i++){ 8 for(int j=0;j<=N;j++){ 9 b[j]+=a[j]; 10 for(int k=i;j+k<=N;k+=i){ 11 b[j+k]+=a[j]; 12 } 13 } 14 for(int j=0;j<=N;j++) 15 a[j]=b[j],b[j]=0; 16 } 17 printf("%d\n",a[N]); 18 } 19 return 0; 20 }
Description
Bessie has gone to the mall's jewelry store and spies a charm bracelet. Of course, she'd like to fill it with the best charms possible from the?N?(1 ≤?N?≤ 3,402) available charms. Each charm?i?in the supplied list has a weight?Wi?(1 ≤?Wi?≤ 400), a 'desirability' factor?Di?(1 ≤?Di?≤ 100), and can be used at most once. Bessie can only support a charm bracelet whose weight is no more than?M?(1 ≤?M?≤ 12,880).
Given that weight limit as a constraint and a list of the charms with their weights and desirability rating, deduce the maximum possible sum of ratings.
Input
* Line 1: Two space-separated integers:?N?and?M
* Lines 2..N+1: Line?i+1 describes charm?i?with two space-separated integers:?Wi?and?Di
Output
* Line 1: A single integer that is the greatest sum of charm desirabilities that can be achieved given the weight constraints
Sample Input
4 6 1 4 2 6 3 12 2 7
Sample Output
23
代碼：
1 #include<stdio.h> 2 #include<string.h> 3 const int MAXN=200000; 4 int bag[MAXN]; 5 #define MAX(x,y)(x>y?x:y) 6 struct Node{ 7 int w,v; 8 }; 9 Node dt[5000]; 10 int main(){ 11 int N,M; 12 while(~scanf("%d%d",&N,&M)){ 13 memset(bag,0,sizeof(bag)); 14 for(int i=0;i<N;i++)scanf("%d%d",&dt[i].w,&dt[i].v); 15 for(int i=0;i<N;i++){ 16 for(int j=M;j>=dt[i].w;j--){ 17 bag[j]=MAX(bag[j],bag[j-dt[i].w]+dt[i].v); 18 } 19 } 20 printf("%d\n",bag[M]); 21 } 22 return 0; 23 }
?
