poj 1745问题
题意：给你n个整数，和一个k值（2<=k<=100)，问在这n个数之间的n-1的位置任意放加减号，问有没有一种情况使结果整除k。
思路：? dp[i][j]=dp[i-1][j-a[i]]||dp[i-1][j+a[i]];这里用到了数论里的一点知识，sum(a[i])%k = sum(a[i]%k)%k,假设dp[i][j]为取前i个数求和时余数为j的情况。只要dp[4][0]=1就表示能够整除。
代码如下：
#include <iostream>using namespace std;int a[10001];int dp[10001][101];int main(){int n,m,s,t,i,j;cin>>n>>m;for(i=1;i<=n;i++)cin>>a[i];s=a[1];while(s<0)s+=m;dp[1][s%m]=1;for (i=2;i<=n;i++){for (j=0;j<m;j++){s=j-a[i];while(s<0)s+=m;t=j+a[i];while(t<0)t+=m;dp[i][j]=dp[i-1][s%m]||dp[i-1][t%m];//状态转移方程}}if (dp[n][0])cout<<"Divisible"<<endl;elsecout<<"Not Divisible"<<endl;return 0;}?