WUST OJ 1349 TLE（简单DP）_综合

[Submit][Status][Web Board]

Description

WH在刷题时，设计出了如下代码：

#include<stdio.h>

int main()

{

int i,j,cnt,k,N,K,a[5555];

scanf("%d%d",&N,&K);

int ans=0;

for(i=1;i<=N;i++) scanf("%d",&a[i]);

for( i=1;i<=N;i++)

for(j=i+1;j<=N;j++)

{

cnt=0;

for( k=i;k<=j;k++) cnt+=a[k];

if(cnt%K==0) ans++;

}

printf("%d\n",ans);

}

上面的代码据说可能会TLE（不管你信不信，反正我是信了，不信你复制粘贴上去看看？）你的任务是重新设计一个更高效的程序帮助WH计算出ans的值

Input

第一行2个整数 N K N<= 5000 K>0

第二行N个数a[i]：第i个数为a[i] 0<= a[i]<= 10000

Output

输出ans的值

Sample Input

5 1
1 2 3 4 5

Sample Output

【题解】发表这个题只是因为我第一次做的时候TLE了很多遍，虽然这个题目就是TLE，今天突然又看见了，心想又多学了一些了是不是可以搞定它了，试了一下就过了，纯粹是为了证明我这段时间的DP知识没白学，已经基本掌握了一些了，简单点的基础的都可以做了，哈哈哈~

水题AC

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
#define ll long long
int dp[5003][5003];
int a[5003];int main()
{int m,k;while(~scanf("%d%d",&m,&k)){ll ans=0;for(int i=0;i<m;i++)scanf("%d",&a[i]);for(int i=0;i<m;i++){dp[i][i]=a[i];for(int j=i+1;j<m;j++){dp[i][j]=dp[i][j-1]+a[j];if(dp[i][j]%k==0) ans++;}}printf("%lld\n",ans);}
}